[LeetCode] (366) Find Leaves of Binary Tree

Source

Basic Idea: since we strip one layer of leaves at a time, the time when a middle node got stripped is based on the height of its taller children as the taller the children, the later the node got striped. Using a default dictionary, store a list of node values for each height, and construct the solution at the end.

class Solution(object):
    def findLeaves(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        self.d = collections.defaultdict(list)
        def dfs(node):
            """
            Returns the height of node, also adds the value
            of the node to the corresponding height in the dictionary.
            """
            if not node:
                return -1
            else:
                height = 1 + max(dfs(node.left), dfs(node.right))
                self.d[height].append(node.val)
                return height
        dfs(root)
        return [self.d[height] for height in sorted(self.d)]

Related posts