LeetCode 872: Leaf-Similar Trees Solution

Master LeetCode problem 872 (Leaf-Similar Trees), a easy challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

872. Leaf-Similar Trees

Easy

Tree Depth-First Search Binary Tree

Problem Explanation

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.

Solution Code

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);
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 872 (Leaf-Similar Trees)?

This page provides optimized solutions for LeetCode problem 872 (Leaf-Similar Trees) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 872 (Leaf-Similar Trees)?

The time complexity for LeetCode 872 (Leaf-Similar Trees) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 872 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 872 in Java, C++, or Python.

Back to LeetCode Solutions