872. Leaf-Similar Trees

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

1. 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.
2. 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, return false.

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, [])
};