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

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

          1

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

          []

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

S： recursion O(n)

根据recursion层数判断当前node应该返回数组中的位置

class Solution {
public:
    vector<vector<int>> findLeaves(TreeNode* root) {
        vector<vector<int>> result;
        dfs(root, result);
        return result;
    }

private:
    int dfs(TreeNode* root, vector<vector<int>>& result) {
        if (!root) return -1;
        int idx = max(dfs(root->left, result), dfs(root->right, result)) + 1;
        if (idx < result.size()) {
            result[idx].push_back(root->val);
        } else {
            result.push_back(vector<int>{root->val});
        }
        return idx;
    }
};