Two backups of the same tree should be identical: the same shape, with the same value in every matching position.
TreeNode(val, left=None, right=None) is in the starter. Keep it.
Write trees_match(a, b) -> bool: True when the trees rooted at a and b have exactly the same structure and the same values in the same places. Two empty trees (None) match.
# a: 4 b: 4 c: 4
# / \ / \ / \
# 2 7 2 7 7 2
trees_match(a, b) # True
trees_match(a, c) # False: the children are swapped
# d: 1 e: 1
# / \
# 3 3
trees_match(d, e) # False: same values, different shape
trees_match(None, None) # True
- Each tree has up to 5,000 nodes; values are arbitrary integers and may repeat.
- Aim for O(n) time, and stop early once you find a difference.
Show hint
Two trees match when their roots match and their left subtrees match and their right subtrees match. Decide what happens when one or both sides are empty.