Given the roots p and q of two binary trees, return true if the trees are identical: they have exactly the same shape and every pair of matching nodes holds the same value.
- Each tree has 0 to 100 nodes
- -10^4 <= Node.val <= 10^4
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
A tempting shortcut is to compare the inorder lists of the two trees, but [1,2] and [1,null,2] show that different shapes can produce identical sequences. The reliable way is to walk both trees together. At each step the two current nodes must either both be missing, or both exist with the same value; then the same must hold recursively for the left pair and the right pair. The first mismatch ends the walk.
Algorithm
- If both
pandqare null, returntrue. - If only one is null, or
p.val != q.val, returnfalse. - Return
isSameTree(p.left, q.left) and isSameTree(p.right, q.right).
O(min(n, m))Space: O(min(h1, h2)) recursion depthisSameTree with the small tree. Interviewers often ask that as the next question.class Solution: def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool: if p is None and q is None: return True if p is None or q is None or p.val != q.val: return False return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)