100. Same Tree
Your function receives p and q, the roots of two binary trees (each node has an integer val plus left and right child pointers; either root may be absent). Return true when the two trees are identical — the same shape, with equal values at every corresponding position — and false otherwise.
Having the same values is not enough: a node that hangs off the left in one tree and off the right in the other makes the trees different, even if nothing else changes (see the figure).
Two empty trees count as identical.
Example 1:
Input: p = [1, 2, 3], q = [1, 2, 3]
Output: true
Explanation: Both trees have root 1 with left child 2 and right child 3 — every position matches.
Example 2:
Input: p = [1, 2], q = [1, null, 2]
Output: false
Explanation: Both trees contain the values 1 and 2, but the 2 hangs left in the first tree and right in the second — the shapes differ.
Constraints:
- 0 ≤ number of nodes in each tree ≤ 1000
- -10⁴ ≤ node value ≤ 10⁴
Hints:
Compare the trees position by position. At any pair of positions there are only three cases: both absent (fine), exactly one absent or values differ (fail), or both present and equal (keep going).
That case analysis is naturally recursive: two trees match iff their roots agree AND the left subtrees match AND the right subtrees match. An explicit stack or queue of node pairs gives the same walk without recursion.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: p = [1, 2, 3], q = [1, 2, 3]
Expected output: true