Leaf-Similar Trees
The key idea
A leaf is a node with no children. Read the leaves of each tree left to right to form its leaf value sequence. Two trees are leaf-similar exactly when these two sequences are identical, so the problem reduces to collecting each tree's leaves in order and comparing the lists. The tree shapes can differ wildly; only the ordered leaf values matter.
Problem
Consider all the leaves of a binary tree. From left to right order, the values of those leaves form a leaf value sequence. Two binary trees are considered leaf-similar if their leaf value sequence is the same. Given the roots of two binary trees root1 and root2, return true if and only if the two given trees with head nodes root1 and root2 are leaf-similar.
Constraints
- The number of nodes in each tree will be in the range [1, 200].
- Both of the given trees will have values in the range [0, 200].
Examples
Input: root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
Output: true
Input: root1 = [1,2,3], root2 = [1,3,2]
Output: false
Complexity
Time: O(n + m) Space: O(n + m)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Tree / Recursion problems
- Balanced Binary TreeEASY
- Binary Tree CamerasHARD
- Binary Tree Inorder TraversalEASY
- Binary Tree Maximum Path SumHARD
- Binary Tree PathsEASY
- Binary Tree Postorder TraversalEASY
- Binary Tree Preorder TraversalEASY
- House Robber IIIMEDIUM
- Construct Binary Tree from Inorder and Postorder TraversalMEDIUM
- Construct Binary Tree from Preorder and Inorder TraversalMEDIUM
- Convert BST to Greater TreeMEDIUM
- Count Complete Tree NodesEASY