572. Subtree of Another Tree
1. Description
Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node’s descendants. The tree s could also be considered as a subtree of itself.
2. Solutions
My Accepted Solution
m is the number of nodes in i_bigTree, n is the number of nodes in i_smallTree
Time complexity: O(mn)
Space complexity: O(n)
class Solution
{
private:
bool isEqualTree(TreeNode *i_bigTree, TreeNode *i_smallTree)
{
if(!i_bigTree && !i_smallTree) return true;
if(!i_bigTree || !i_smallTree) return false;
return (i_bigTree->val == i_smallTree->val
&& isEqualTree(i_bigTree->left, i_smallTree->left)
&& isEqualTree(i_bigTree->right, i_smallTree->right)
);
}
public:
// public boolean isSubtree(TreeNode s, TreeNode t)
bool isSubtree(TreeNode *i_bigTree, TreeNode *i_smallTree)
{
// we could check the result and when find a valid solution, return immediatelly
bool isLeftSubtree = false, isRightSubtree = false, isCurrentSubtree = false;
if(i_bigTree && i_smallTree && i_bigTree->val == i_smallTree->val)
isCurrentSubtree = isEqualTree(i_bigTree, i_smallTree);
if(i_bigTree->left)
isLeftSubtree = isSubtree(i_bigTree->left, i_smallTree);
if(i_bigTree->right)
isRightSubtree = isSubtree(i_bigTree->right, i_smallTree);
return isCurrentSubtree | isLeftSubtree | isRightSubtree;
}
};