Similar Problems

Similar Problems not available

Find Leaves Of Binary Tree - Leetcode Solution

Companies:

  • google

LeetCode:  Find Leaves Of Binary Tree Leetcode Solution

Difficulty: Medium

Topics: tree binary-tree depth-first-search  

The problem "Find Leaves of Binary Tree" on LeetCode asks us to find and remove the leaves of a given binary tree, from left to right. A leaf node is a node with no children.

We can start by using a recursive approach to traverse the binary tree. We can pass a list to keep track of the leaves as we find them. The base case for recursion is when we reach a leaf node, we append it to the list and remove it from the tree. Once all leaves are removed, the tree would be empty.

To implement this approach in Python:

def findLeaves(root):
    leaves = []
    def helper(node):
        if not node:
            return -1
        left = helper(node.left)
        right = helper(node.right)
        level = max(left, right) + 1
        if level == len(leaves):
            leaves.append([])
        leaves[level].append(node.val)
        return level
    helper(root)
    return leaves

In the above code, we use a helper function to traverse the binary tree recursively. We pass in the root node and the list to keep track of the leaves.

Inside the helper function, we check if the current node is null. If it is, we return -1.

We recursively call the helper function on the left and right children of the node. We get the level of the current node by adding 1 to the maximum level between the left and right subtree.

If the list of leaves has the same length as the level, we append a new empty list to the list of leaves.

Finally, we append the value of the current node to the appropriate level in the list of leaves and return the level.

The leaves list will contain a list of lists, where each inner list contains the values of the nodes at the same level. We can return the leaves list.

Find Leaves Of Binary Tree Solution Code

1