给你一棵二叉树,请按以下要求的顺序收集它的全部节点:
示例:
输入: [1,2,3,4,5]
1
/ \
2 3
/ \
4 5
输出: [[4,5,3],[2],[1]]
解释:
1. 删除叶子节点 [4,5,3] ,得到如下树结构:
1
/
2
2. 现在删去叶子节点 [2] ,得到如下树结构:
1
3. 现在删去叶子节点 [1] ,得到空树:
[]
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/find-leaves-of-binary-tree 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
类似题目:LeetCode 156. 上下翻转二叉树(DFS)*
class Solution {
vector<vector<int>> ans;
queue<TreeNode*> q;
unordered_map<TreeNode*, int> map;//父节点底下挂着几个子节点
public:
vector<vector<int>> findLeaves(TreeNode* root) {
reverse(root);//上下翻转二叉树
while(!q.empty())
{
int size = q.size(), i = 0;
vector<int> lv(size);
while(size--)
{
TreeNode *cur = q.front();
q.pop();
map[cur->left]--;//原父节点的子节点计数-1
lv[i++] = cur->val;//当前值写入答案
if(cur->left && map[cur->left]==0)//父节点计数为0,可以入队
q.push(cur->left);
}
ans.push_back(lv);
}
return ans;
}
TreeNode* reverse(TreeNode* root)
{
if(!root) return NULL;
auto l = root->left;
auto r = root->right;
if(!l && !r)
q.push(root);//叶子节点加入队列
map[root] += (l?1:0) + (r?1:0);//记得加括号,子节点个数
root->left = NULL;//断开子节点
root->right = NULL;
auto lc = reverse(l);
auto rc = reverse(r);
if(lc)
lc->left = root;//子节点的left指向父节点
if(rc)
rc->left = root;
return root;
}
};
0 ms 9 MB
class Solution {
vector<vector<int>> ans;
public:
vector<vector<int>> findLeaves(TreeNode* root) {
dfs(root);
return ans;
}
int dfs(TreeNode* root)
{
if(!root) return -1;
int hl = dfs(root->left);
int hr = dfs(root->right);
int hcur = max(hl, hr) + 1;
if(ans.size() <= hcur)
ans.push_back({});
ans[hcur].push_back(root->val);
return hcur;
}
};
4 ms 9.1 MB