
Description
Given two binary trees, the task is to determine if they are leaf-similar. Two binary trees are considered leaf-similar if their leaf value sequence is the same. The leaf value sequence is the sequence of values of the leaves from left to right.
Intuition
The core idea behind this problem is that the structure of the trees is not as important as the sequence of their leaf nodes. The leaves of a tree are the nodes that do not have any children. By traversing both trees and collecting their leaf values in order, we can directly compare the sequences to determine if the trees are leaf-similar.
Approach
- Leaf Collection: Traverse both trees to collect the leaf nodes. The traversal method can be either DFS or BFS. In this case, DFS is typically used to easily retrieve leaf nodes in a left-to-right order.
- Comparison: After collecting the leaf values from both trees, compare the two sequences. If the sequences match, the trees are leaf-similar; otherwise, they are not.
Detailed Steps:
- Implement a helper function to perform a depth-first search (DFS) on each tree. This function will collect the values of all leaf nodes.
- Invoke this helper function on both trees to get their respective leaf sequences.
- Compare the two sequences. If they are identical, return
true
, indicating the trees are leaf-similar. Otherwise, returnfalse
.
Complexity
Time Complexity:
O(N), where N is the number of nodes in the larger tree. Each node is visited exactly once during the DFS.
Space Complexity:
O(H), where H is the height of the tree. This is the space used by the recursion stack during DFS. The leaf storage requires O(L) space, where L is the number of leaves, but this is generally much smaller than the recursion stack usage.
Code
C++
class Solution {
public:
bool leafSimilar(TreeNode* root1, TreeNode* root2) {
vector leafs1, leafs2;
std::function&)> dfs = [&](TreeNode* node, vector& leafs) {
if (!node) return;
if (!node->left && !node->right) {
leafs.push_back(node->val);
}
dfs(node->left, leafs);
dfs(node->right, leafs);
};
dfs(root1, leafs1);
dfs(root2, leafs2);
return leafs1 == leafs2;
}
};
Python
class Solution:
def leafSimilar(self, root1: TreeNode, root2: TreeNode) -> bool:
def dfs(node, leafs):
if not node:
return
if not node.left and not node.right:
leafs.append(node.val)
dfs(node.left, leafs)
dfs(node.right, leafs)
leafs1 = []
leafs2 = []
dfs(root1, leafs1)
dfs(root2, leafs2)
return leafs1 == leafs2
Java
class Solution {
private void dfs(TreeNode node, List leafs) {
if (node == null) return;
if (node.left == null && node.right == null) {
leafs.add(node.val);
}
dfs(node.left, leafs);
dfs(node.right, leafs);
}
public boolean leafSimilar(TreeNode root1, TreeNode root2) {
List leafs1 = new ArrayList<>();
List leafs2 = new ArrayList<>();
dfs(root1, leafs1);
dfs(root2, leafs2);
return leafs1.equals(leafs2);
}
}
JavaScript
/**
* @param {TreeNode} root1
* @param {TreeNode} root2
* @return {boolean}
*/
var leafSimilar = function (root1, root2) {
function dfs(node, leafs) {
if (!node) return null
if (!node.left && !node.right) {
leafs.push(node.val)
}
dfs(node.left, leafs)
dfs(node.right, leafs)
return leafs.join(',')
}
return dfs(root1, []) === dfs(root2, [])
};