Find Leaves of Binary Tree

Problem Id: 366 Difficulty: Medium Tag: Tree Tag: Depth-first Search


Intuition

Let's define a variable called level_from_leaf. For leaves, this value is 0. For other nodes, level[node] = max(level[node.left], level[node.right]) + 1. So we could use DFS and Dynamic Programming to solve this problem.

Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def findLeaves(self, root: TreeNode) -> List[List[int]]:
        self.result = []
        self._helper(root)
        return self.result

    def _helper(self, node):
        if node is None:
            return -1
        l = self._helper(node.left)
        r = self._helper(node.right)
        level = max(l, r) + 1
        while len(self.result) <= level:
            self.result.append([])
        self.result[level].append(node.val)
        return level