535. Leaf-Similar Trees
Read off the leaves of a binary tree from left to right and you get its leaf signature — the ordered list of values sitting on nodes with no children. Two trees are called leaf-similar when their leaf signatures are exactly the same list, in the same order, regardless of how different the trees look on the inside.
You are given the roots of two binary trees, root1 and root2. Return true if the two trees are leaf-similar and false otherwise.
Example 1:
Input: root1 = [3, 5, 1, 6, 2, 9, 8], root2 = [10, 4, 8, 6, 2, 9, 8]
Output: true
Explanation: Both trees have the leaf signature [6, 2, 9, 8] when leaves are read left to right, so they are leaf-similar even though their internal nodes (3, 5, 1 versus 10, 4, 8) differ completely.
Example 2:
Input: root1 = [1, 2, 3], root2 = [1, 3, 2]
Output: false
Explanation: The first tree's leaves read [2, 3]; the second's read [3, 2]. Same values, wrong order — the signatures must match as sequences, not as sets.
Constraints:
- 1 ≤ number of nodes in each tree ≤ 200
- 0 ≤ Node.val ≤ 200
Hints:
A leaf is a node with no left child and no right child. Any depth-first traversal that explores left before right will meet the leaves in exactly left-to-right order.
Collect each tree's leaf values into its own list with one DFS per tree, then compare the two lists for equality — order and length both matter.
Follow-up: can you avoid materializing both lists? Keep one explicit stack per tree, repeatedly advance each to its next leaf, and compare on the fly.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root1 = [3, 5, 1, 6, 2, 9, 8], root2 = [10, 4, 8, 6, 2, 9, 8]
Expected output: true