Twin Trees
EasyTrees
Problem
Two replicas of a configuration tree are supposed to be identical. Given the roots a and b, return true if they have exactly the same shape and the same value at every corresponding position, false otherwise.
Example 1
- Input:
- a = [1, 2, 3], b = [1, 2, 3]
- Output:
- true
Example 2
- Input:
- a = [1, 2], b = [1, null, 2]
- Output:
- false
The 2 hangs on the left in one tree and on the right in the other.
Example 3
- Input:
- a = [1, 2, 1], b = [1, 1, 2]
- Output:
- false
Constraints
- 0 ≤ nodes in each tree ≤ 10^4
- -10^4 ≤ node.val ≤ 10^4
Hint
Show the first hint
Two empty trees are identical. When is a pair of nodes definitely different?
Walkthrough
How to approach it
01Clarify before coding
- Does 'same' include shape? Yes: equal values in different positions do not count.
- Can either tree be empty? Yes; two empty trees are the same.
- Can values repeat? Yes, so you cannot compare sets of values.
02Brute force
Serialize both trees to strings including null markers and compare the strings.
Cost: O(n + m) time but O(n + m) extra memory for the strings, and it does all the work even when the roots already differ.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.