Problem

Consider all the leaves of a binary tree, from left to right order, the values of those leaves form a leaf value sequence.

graph TD;
	A(3) --- B(5) & C(1)
	B --- D(6) & E(2)
	E --- F(7) & G(4)
	C --- H(9) & I(8)

 style D fill:#4682B4,stroke:#333,stroke-width:2px
 style F fill:#4682B4,stroke:#333,stroke-width:2px
 style G fill:#4682B4,stroke:#333,stroke-width:2px
 style H fill:#4682B4,stroke:#333,stroke-width:2px
 style I fill:#4682B4,stroke:#333,stroke-width:2px

For example, in the given tree above, the leaf value sequence is (6, 7, 4, 9, 8).

Two binary trees are considered leaf-similar if their leaf value sequence is the same.

Return true if and only if the two given trees with head nodes root1 and root2 are leaf-similar.

Examples

Example 1:

---
title: root1
---
graph TD;
	A(3) --- B(5) & C(1)
	B --- D(6) & E(2)
	E --- F(7) & G(4)
	C --- H(9) & I(8)

style D fill:#4682B4,stroke:#333,stroke-width:2px
style F fill:#4682B4,stroke:#333,stroke-width:2px
style G fill:#4682B4,stroke:#333,stroke-width:2px
style H fill:#4682B4,stroke:#333,stroke-width:2px
style I fill:#4682B4,stroke:#333,stroke-width:2px
  
---
title: root2
---

graph TD;
	A(3) --- B(5) & C(1)
	B --- D(6) & E(7)
	C --- H(4) & I(2)
	I --- F(9) & G(8)


style D fill:#4682B4,stroke:#333,stroke-width:2px
style E fill:#4682B4,stroke:#333,stroke-width:2px
style G fill:#4682B4,stroke:#333,stroke-width:2px
style H fill:#4682B4,stroke:#333,stroke-width:2px
style F fill:#4682B4,stroke:#333,stroke-width:2px
  
1
2
3
4

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

Example 2:

---
title: root1
---
graph TD;
	A(1) --- B(2) & C(3)


style B fill:#4682B4,stroke:#333,stroke-width:2px
style C fill:#4682B4,stroke:#333,stroke-width:2px
  
---
title: root2
---
graph TD;
	A(1) --- B(3) & C(2)


style B fill:#4682B4,stroke:#333,stroke-width:2px
style C fill:#4682B4,stroke:#333,stroke-width:2px
  
1
2
3
4

Input:
root1 = [1,2,3], root2 = [1,3,2]
Output:
 false

Solution

Method 1 - DFS

To solve this problem, we need to compare the leaf values of two binary trees. The approach involves performing a depth-first traversal(pre-order) on each tree to collect the leaf values sequentially. After obtaining the leaf values from both trees, we can compare the sequences to determine their similarity.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

public class Solution {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List<Integer> leafValues1 = new ArrayList<>();
        List<Integer> leafValues2 = new ArrayList<>();
        
        collectLeafValues(root1, leafValues1);
        collectLeafValues(root2, leafValues2);

        return leafValues1.equals(leafValues2);
    }

    private void collectLeafValues(TreeNode root, List<Integer> leafValues) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            leafValues.add(root.val);
        }
        collectLeafValues(root.left, leafValues);
        collectLeafValues(root.right, leafValues);
    }
}

Complexity

  • Time: O(n1+n2) where n1 and n2 are number of nodes in tree1 and tree 2.
  • Space: O(h1 + h2) where h1 and h2 are the heights of the two trees, assuming recursion stack during the depth-first traversal.