Comparing two trees at once
To check that two trees are identical, walk them together in lockstep, like two people following the same directions and comparing what they see at every turn.
At each step you look at one spot in each tree and ask two questions: do both have a node there, and do the nodes hold the same value?
Both empty: both trees ended at the same point: same.
Only one empty: one tree has a node and the other doesn't: different.
p = [1, 2, 3] on the left, q = [1, 2, 3] on the right
Walk both trees in lockstep. Roots: both exist, both hold 1. So far so good.
Move 1 of 4
The recursive step
If neither spot is empty and the two values match, then the trees are identical only if the left subtrees match each other and the right subtrees match each other. Both sides must be the same. A single mismatch anywhere means the answer is no.
Different numbers: in the same position means the trees differ.
Both sides: the left pair and the right pair must both be the same.
if not p and not q:
return True
if not p or not q:
return False
if p.val != q.val:
return False
left = is_same_tree(p.left, q.left)
right = is_same_tree(p.right, q.right)
return left and right