466. Leaf Sequence Match
Two seed catalogues are stored as binary trees a and b. When you walk a tree from left to right and write down the value of every leaf (a node without children) as you meet it, you get that tree's leaf sequence. Two catalogues are considered equivalent when their leaf sequences are exactly the same, even if the trees have completely different shapes or internal values.
Return true if the leaf sequence of a equals the leaf sequence of b, otherwise return false. The order of the leaves matters and repeated values are kept.
Example 1
- Input:
- a = [5,2,8,4,null,6,9], b = [1,4,3,null,null,6,9]
- Output:
- true
- Explanation:
Both trees have leaves 4, 6, 9 from left to right, even though their shapes differ.
Example 2
- Input:
- a = [5,2,8,4,null,6,9], b = [7,6,4,9]
- Output:
- false
- Explanation:
The second tree's leaves read 9, 4 while the first reads 4, 6, 9, so they differ.
Constraints
1 ≤ number of nodes in each of a and b ≤ 1000
0 ≤ Node.val ≤ 200
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n + m)
- Space
- O(n + m)