Same Tree
- 1 min read
- LC-Easy
- Binary Tree
3 years ago
Solution
- Recursive function, go one node at a time
- If both nodes are null, subtree is equal
- If one node is null and the other isn't, they aren't equal
- If both nodes have same value are the rest of the child subtrees are equal, the nodes are equal
| Time | Space | Explanation |
|---|---|---|
O(n) | O(log n) or O(h) |
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
if not p and not q:
return True
if (p and not q) or (q and not p):
return False
if p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right):
return True