Python solution with just LIST (33ms)


  • 0

    If you think into this question, you will find that every time when we remove the leaves, we actually remove the nodes with the same height. Therefore, we could first try to calculate the height of each node in the tree, then collect the nodes with the same height again and again.

    However, we could do this efficiently since when we calculate the height, we do it in the recursive way, that is, the nodes with smaller height is always calculated before the nodes with greater height.

    As a result, we could do all this work in one run.

    def findLeaves(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        def getHeight(node):
            if not node: return -1
            
            leftHeight = getHeight(node.left)
            rightHeight = getHeight(node.right)
            thisHeight = max(leftHeight, rightHeight) + 1
            
            if thisHeight < len(ans):
                ans[thisHeight].append(node.val)
            else:
                ans.append([])
                ans[-1].append(node.val)
            return thisHeight
        # get height of each node in the tree
        ans = []
        getHeight(root)
        return ans
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.