The problem
Given the roots of two binary trees, p and q, return true if they are the same: the same shape, with the same values in the same places.
Examples
01
- Input
p = [1, 2, 3], q = [1, 2, 3]
- Output
true
02
- Input
p = [1, 2], q = [1, null, 2]
- Output
false
03
- Input
p = [1, 2, 1], q = [1, 1, 2]
- Output
false
Constraints
- 0 ≤ nodes in each tree ≤ 100
- −10⁴ ≤ Node.val ≤ 10⁴
The idea
Two trees are the same when both are empty, or when both roots hold the same value and the left subtrees are the same and the right subtrees are the same.
Walk both together. The first mismatch — one node missing where the other exists, or two different values — answers false at once.
- Time
- O(n) — each pair of nodes compared once
- Space
- O(h)
Solution · every language run against every case
class Solution: def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool: if not p or not q: return p is q # both empty, or one is missing return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)