Description
Determine whether two trees have identical structure and values.
Solution
def is_same_tree(p, q):
if not p or not q:
return p is q
return p.val == q.val and is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)Examples
Example 1
- Input
[[1,2],[1,2]]- Output
true
Both values and positions match.
Example 2
- Input
[[1,2],[1,null,2]]- Output
false
The value 2 appears on opposite sides.
Example 3
- Input
[[],[]]- Output
true
Two empty trees are identical.
Approach
Compare roots, then compare corresponding children recursively.
Time & space
O(min(n,m)) time in the worst matching prefix; O(min(h,g)) recursion space for node counts n,m and tree heights h,g.