Given the roots of two binary trees p and q, decide whether the trees are identical: the same shape with the same values in the same places. Two empty trees are the same.
Examples
Example 1:
Input: p = [1,2,3], q = [1,2,3]
Output: true
Example 2:
Input: p = [1,2], q = [1,null,2]
Output: false
Explanation: same values, different shape — the 2 hangs on different sides.
Example 3:
Input: p = [1,2,1], q = [1,1,2]
Output: false
Example 4:
Input: p = [], q = []
Output: true
Constraints
0 <= number of nodes in each tree <= 100
-10^4 <= Node.val <= 10^4
Prerequisites
Binary trees, and recursion over them: solve the children, combine, return. The base case is almost always the empty tree. Depth-first order (pre, in, post) and breadth-first by level — and knowing which one a problem is really asking for.
How to think about it
1. Walk Both in Lockstep Optimal
Intuition
Two trees are identical when their roots match and their corresponding subtrees are identical — the recursion mirrors the definition exactly. Putting the both-empty case first is what makes the rest short: after it, one being empty is an immediate no.
Algorithm
1. Both empty: identical. 2. Exactly one empty, or values differ: not identical. 3. Otherwise both left subtrees and both right subtrees must be identical.
Time & Space
Time O(min(n, m)) — the walk stops at the first difference. Space O(h).