LeetCode 366: Find Leaves of Binary Tree Solution

Master LeetCode problem 366 (Find Leaves of Binary Tree), a medium 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.

366. Find Leaves of Binary Tree

Medium

Tree Depth-First Search Binary Tree

Problem Explanation

Explanation

To find leaves of a binary tree, we can repeatedly remove the leaves until the tree becomes empty. At each step, we identify and remove all the leaves (nodes with no children) from the tree and store them in a separate list. We repeat this process until there are no more leaves left in the tree.

Algorithm:

Create a function findLeaves that takes the root of the binary tree as input.
Initialize an empty list to store the leaves.
Repeat the following steps until the tree becomes empty:
- Create a helper function dfs that returns the height of the current node.
- If the current node is a leaf (i.e., both left and right children are null), add it to the list of leaves and return 0.
- Otherwise, calculate the height of the current node as 1 + max(height of left child, height of right child).
Remove the leaves that were identified in each iteration from the tree.
Continue this process until all leaves are removed from the tree.

Time Complexity:

The time complexity of this algorithm is O(n^2), where n is the number of nodes in the binary tree.

Space Complexity:

The space complexity of this algorithm is O(n), where n is the number of nodes in the binary tree.

Solution Code

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public List<List<Integer>> findLeaves(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        while (root != null) {
            List<Integer> leaves = new ArrayList<>();
            root = removeLeaves(root, leaves);
            result.add(leaves);
        }
        return result;
    }
    
    private TreeNode removeLeaves(TreeNode node, List<Integer> leaves) {
        if (node == null) return null;
        if (node.left == null && node.right == null) {
            leaves.add(node.val);
            return null;
        }
        node.left = removeLeaves(node.left, leaves);
        node.right = removeLeaves(node.right, leaves);
        return node;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 366 (Find Leaves of Binary Tree)?

This page provides optimized solutions for LeetCode problem 366 (Find Leaves of Binary Tree) 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 366 (Find Leaves of Binary Tree)?

The time complexity for LeetCode 366 (Find Leaves of Binary Tree) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 366 on DevExCode?

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

Back to LeetCode Solutions