Dare2Solve
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.
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.
true
, indicating the trees are leaf-similar. Otherwise, return false
.O(N), where N is the number of nodes in the larger tree. Each node is visited exactly once during the DFS.
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.
class Solution {
public:
bool leafSimilar(TreeNode* root1, TreeNode* root2) {
vector<int> leafs1, leafs2;
std::function<void(TreeNode*, vector<int>&)> dfs = [&](TreeNode* node, vector<int>& 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;
}
};
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
class Solution {
private void dfs(TreeNode node, List<Integer> 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<Integer> leafs1 = new ArrayList<>();
List<Integer> leafs2 = new ArrayList<>();
dfs(root1, leafs1);
dfs(root2, leafs2);
return leafs1.equals(leafs2);
}
}
/**
* @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, [])
};