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:

Given binary tree 

1         / \        2   3       / \           4   5

 

Returns [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:

[]

 

 

Returns [4, 5, 3], [2], [1].

 

 

 

1 /** 2  * Definition for a binary tree node. 3  * public class TreeNode { 4  *     public int val; 5  *     public TreeNode left; 6  *     public TreeNode right; 7  *     public TreeNode(int x) { val = x; } 8  * } 9  */10 public class Solution {11     public IList
     
      
       > FindLeaves(TreeNode root) {12         var result = new List
       
        
         >();13         if (result == null) return result;14         15         Height(root, result);16         return result;17     }18     19     private int Height(TreeNode node, IList
         
          
           > result)20 {21 if (node == null) return -1;22 int h = 1 + Math.Max(Height(node.left, result), Height(node.right, result));23 24 if (h >= result.Count)25 {26 result.Add(new List
           
            ());27 }28 29 result[h].Add(node.val);30 31 return h;32 }33 }34 35 public class Solution1 {36 public IList
            
             
              > FindLeaves(TreeNode root) {37 var result = new List
              
               
                >();38 if (result == null) return result;39 40 var leaves = new HashSet
                
                 ();41 leaves.Add(null);42 43 while (!leaves.Contains(root))44 {45 var list = new List
                 
                  ();46 DFS(root, leaves, list);47 result.Add(list);48 }49 50 return result;51 }52 53 private void DFS(TreeNode node, HashSet
                  
                    leaves, IList
                   
                     result)54 {55 if (leaves.Contains(node)) return;56 if (leaves.Contains(node.left) && leaves.Contains(node.right))57 {58 result.Add(node.val);59 leaves.Add(node);60 return;61 }62 63 DFS(node.left, leaves, result);64 DFS(node.right, leaves, result);65 }66 }