Dare2Solve
The problem requires comparing two binary trees node by node. If both nodes are None
, they are the same. If only one of them is None
, they are not the same. If the values of the nodes are different, they are not the same. Otherwise, we need to check the left and right subtrees recursively.
Base Case:
p
and q
are None
, return True
because two empty trees are the same.p
or q
is None
, or the values at the current nodes are different, return False
.Recursive Case:
p
and q
by calling isSameTree(p.left, q.left)
.p
and q
by calling isSameTree(p.right, q.right)
.True
if both the left and right subtrees are the same, otherwise return False
.O(N), where N is the number of nodes in the binary trees. Each node is visited once.
O(H), where H is the height of the tree. This is due to the space required for the recursion stack. In the worst case (for a completely unbalanced tree), the height is N, and in the best case (for a completely balanced tree), the height is log(N).
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if (!p && !q) {
return true;
}
if (!p || !q || p->val != q->val) {
return false;
} else {
bool lSol = isSameTree(p->left, q->left);
if (lSol) {
return isSameTree(p->right, q->right);
} else {
return false;
}
}
}
};
class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
if not p and not q:
return True
if not p or not q or p.val != q.val:
return False
else:
lSol = self.isSameTree(p.left, q.left)
if lSol:
return self.isSameTree(p.right, q.right)
else:
return False
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
}
if (p == null || q == null || p.val != q.val) {
return false;
} else {
boolean lSol = isSameTree(p.left, q.left);
if (lSol) {
return isSameTree(p.right, q.right);
} else {
return false;
}
}
}
}
var isSameTree = function (p, q) {
if (!p && !q) {
return true;
}
if (!q || !p || p.val != q.val) {
return false;
} else {
let lSol = isSameTree(p.left, q.left);
if (lSol) {
return isSameTree(p.right, q.right);
} else {
return false;
}
}
};