366. Find Leaves of Binary Tree

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.

Example:

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

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

Explanation:

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:

          []        

TC: O(n), SC: O(n)
class Solution(object):
    ans = []
    def findLeaves(self, root):
        dfs(root)
        return self.ans

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

---

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)