[LeetCode] (366) Find Leaves of Binary Tree

来源

基本思路:因为每一个节点只要还有子女节点就不会被剥走,所以每一个节点被剥掉的时机是基于它较高的子女树,也就是它自己本身的高度(减一)。用一次深度优先搜索算出所有节点的高度,然后插入字典中相对应的高度,最后通过字典重建答案。

class Solution(object):
    def findLeaves(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        self.d = collections.defaultdict(list)
        def dfs(node):
            """
            返回节点高度,同时将节点值存入字典相对应的高度。
            """
            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