Problem
Given the roots of two binary trees root1 and root2, returntrue if the two trees are leaf-similar. Otherwise, return false.
Two trees are leaf-similar if their leaf value sequences are identical. A leaf is a node that has no left or right child.
Example(s)
Consider the following examples to understand the expected input and output.Example
Input
root1:
3
/ \
5 1
/ \ / \
6 2 9 8
/ \
7 4
root2:
3
/ \
5 1
/ \ / \
6 7 4 2
/ \
9 8Output
trueSolution
This solution uses Depth-First Search (DFS) to traverse both trees and collect their leaf values from left to right.During the traversal, whenever a node has no left or right child, it is a leaf node, so its value is added to the result list. After collecting the leaf sequences from both trees, we compare the two lists.
class Solution {
public boolean leafSimilar(TreeNode root1, TreeNode root2) {
List<Integer> leaves1 = new ArrayList<>();
List<Integer> leaves2 = new ArrayList<>();
dfs(root1, leaves1);
dfs(root2, leaves2);
return leaves1.equals(leaves2);
}
private void dfs(TreeNode node, List<Integer> leaves) {
if (node == null) {
return;
}
if (node.left == null && node.right == null) {
leaves.add(node.val);
return;
}
dfs(node.left, leaves);
dfs(node.right, leaves);
}
}Complexity
Each node in both trees is visited once, so the time complexity isO(n + m), where n and m are the numbers of nodes in the two trees.
The leaf lists and DFS recursion use
O(n + m) space in the worst case.