题目描述

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:

          []         

算法1

(暴力枚举) $O(n^2)$

用remove函数递归的找到叶节点放入数组，然后返回当前node。主函数循环调用remove直至root为空。

时间复杂度

O(n)
O(n) recursive function stack

参考文献

C++ 代码

class Solution {
public:
    vector<vector<int>> findLeaves(TreeNode* root) {
        vector<vector<int>> res;
        while(root)
        {
            vector<int> leaves;
            root=remove(root,leaves);
            res.push_back(leaves);
        }
        return res;
    }
    TreeNode* remove(TreeNode* root, vector<int> &leaves)
    {
        if(!root) return NULL;
        if(!root->left && !root->right)
        {
            leaves.push_back(root->val);
            return NULL;
        }
        root->left=remove(root->left,leaves);
        root->right=remove(root->right,leaves);
        return root;
    }
};