Question
Given two binary trees, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical and the nodes have the same value.
Difficulty:Easy
Category:Tree, Depth-first-Search
Solution
Solution 1: Recursion
Time complexity: O(n) Space complexity: O(n)
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if (!p && !q) return true;
if (!p || !q) return false;
return p->val == q->val && isSameTree(p->left, q->left) &&
isSameTree(p->right, q->right);
}
};
Follow up
如何判断其中一个树是另外一个树的 subtree
Solution: Recursion
Time complexity: O(max(n, m)) Space complexity: O(max(n, m))
class Solution {
public:
bool isSubtree(TreeNode* s, TreeNode* t) {
if (t == nullptr) return true;
if (s == nullptr) return false;
if (isSameTree(s, t)) return true;
return isSubtree(s->left, t) || isSubtree(s->right, t);
}
private:
bool isSameTree(TreeNode* s, TreeNode* t) {
if (s == nullptr && t == nullptr) return true;
if (s == nullptr || t == nullptr) return false;
return (s->val == t->val)
&& isSameTree(s->left, t->left)
&& isSameTree(s->right, t->right);
}
};