Problem
Given the roots of two binary trees p and q, return true if the trees are the same. Otherwise, return false.Two binary trees are considered the same if they have the same structure and the corresponding nodes contain the same values.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
p = [1,2,3]
1
/ \
2 3
q = [1,2,3]
1
/ \
2 3
Output
true Solution
This solution uses Depth-First Search (DFS) with recursion to compare the corresponding nodes of both trees.If both nodes are
null, they are considered equal. If only one node is null, or their values are different, the trees are not the same.
Otherwise, the left children and right children of both nodes are compared recursively. The trees are the same only if all corresponding nodes match.
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
// Both nodes are null
if (p == null && q == null) {
return true;
}
// One node is null
if (p == null || q == null) {
return false;
}
// Compare values and recursively compare subtrees
return p.val == q.val
&& isSameTree(p.left, q.left)
&& isSameTree(p.right, q.right);
}
}
Complexity
Each corresponding node in both trees is visited once, resulting in a time complexity ofO(n), where n is the number of nodes.
The recursive call stack can grow up to the height of the tree, resulting in an extra space complexity of
O(h), where h is the height of the tree.