tree

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

    1
   / 
  2   3
 /      
4   5    

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

• Define a level of a node by its child nodes

• The process of running a test:

  dfs([], node(1))
  dfs([], node(3))
  dfs([], node(NULL))
  return -1 to dfs([], node(3))
  dfs([], node(NULL))
  dfs([], node(3)): level = 1 + max(-1, -1) = 0
  dfs([], node(3)): [ [3]] -> return 0
  dfs([ [3]], node(2))
  dfs([ [3]], node(5))
  dfs([ [3]], node(NULL))
  return -1 to dfs([ [3]], node(5))
  dfs([ [3]], node(NULL))
  return -1 to dfs([ [3]], node(5))
  dfs([ [3]], node(5)) level = 1 + max(-1, -1) = 0
  dfs([ [3]], node(5)): [ [5,3]] -> return 0

• recursion : The easiest way to thinking the process of recursion is first to test the lowermost level.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

int (vector<vector<int>>& res, TreeNode* node){
      if(!node)
          return -1;
      int level = 1 + max(dfs(res, node->right), dfs(res, node->left));
      if(res.size() < level + 1){
          vector<int> subres;
          res.push_back(subres);
      }
      res[level].push_back(node->val);
      return level;
  }

  vector<vector<int>> findLeaves(TreeNode* root) {
      vector<vector<int>> res;
      dfs(res, root);
      return res;
  }