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:
[][[3,5,4],[2],[1]], [[3,4,5],[2],[1]], etc, are also consider correct answers since per each level it doesn't matter the order on which elements are returned.
A:
就是简单的递归,然后返回 到 leaf 的距离
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<vector<int>> findLeaves(TreeNode* root) { vector<vector<int>> res; helper(root, res); return res; } private: int helper(TreeNode* root, vector<vector<int>>& res ){ // return depth to lowest leaf if(not root) return -1; int l = helper(root->left, res); int r = helper(root->right, res); int level = max(l, r)+1; if(res.size() < level + 1){ res.push_back(vector<int>()); } res[level].push_back(root->val); return level; } };
Mistakes:
level 没有+1
No comments:
Post a Comment