366. Find Leaves of Binary Tree

-

https://github.com/openset/leetcode/tree/master/problems/find-leaves-of-binary-tree

https://leetcode.com/problems/find-leaves-of-binary-tree/

https://www.lintcode.com/problem/find-leaves-of-binary-tree/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.

 

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:

          []
-----
Intuition
Need info from both left, and right child to determine if current node is leaf node
Post Order DFS

Consider looking up the tree from below where the level is determined as the height from below 
Terminate recursion when node is null, return -1 so it can contribute to level 0

level = max(left, right) + 1

if level == ans.size()
    ans.add(new ArrayList<Integer>())

ans.add(node.val)
node.left = node.right = null

return level
---
Time - O(N)
Space- O(N) - worst case, skewed tree
---
Related problems
---