Leetcode 366. Find Leaves of Binary Tree (Python)

Related Topic

Depth-First-Search.

Description

Given a binary tree, collect a tree’s nodes as if you were doing this: Collect and remove all leaves, repeat until the tree is empty.

Sample I/O

Example 1

Input: [1,2,3,4,5]
  
          1
         / \
        2   3
       / \     
      4   5    

Output: [[4,5,3],[2],[1]]

1. Removing the leaves [4,5,3] would result in this tree:
          1
         / 
        2   

2. Now removing the leaf [2] would result in this tree:
          1        

3. Now removing the leaf [1] would result in the empty tree:
          []        

Methodology

Use DFS to find the height of the subtree, append all roots with same height in a same list and return the result

Code(DFS)

def findLeaves(self, root):
        def dfs(root):
            if not root:
                return -1
            depth = max(dfs(root.left), dfs(root.right))+1
            if depth == len(res):
                res.append([])
            res[depth].append(root.val)
            return depth
        res = []
        dfs(root)
        return res

BigO

We traversal all elements of the tree once so total time complexity is O(n)