LeetCode 872: Leaf-Similar Trees
Problem Description
Explanation
To solve this problem, we need to perform a depth-first search (DFS) on both trees to extract their leaf values. We can then compare the leaf values of the two trees to determine if they are leaf-similar. The order of leaf values should match from left to right.
- Perform a DFS traversal on each tree to extract the leaf values.
- Compare the leaf values of both trees.
- If the leaf values match, return true; otherwise, return false.
Time complexity: O(n) - where n is the total number of nodes in both trees. Space complexity: O(h) - where h is the height of the tree.
Solutions
class Solution {
public boolean leafSimilar(TreeNode root1, TreeNode root2) {
List<Integer> leafValues1 = new ArrayList<>();
List<Integer> leafValues2 = new ArrayList<>();
dfs(root1, leafValues1);
dfs(root2, leafValues2);
return leafValues1.equals(leafValues2);
}
private void dfs(TreeNode node, List<Integer> leafValues) {
if (node == null) return;
if (node.left == null && node.right == null) {
leafValues.add(node.val);
return;
}
dfs(node.left, leafValues);
dfs(node.right, leafValues);
}
}Related LeetCode Problems
Loading editor...