济南建站公司网站,wordpress framework,嘉兴行业网站建设,学做网站好就业吗文章目录1. 题目2. 解题1. 题目
给你一棵二叉树#xff0c;请按以下要求的顺序收集它的全部节点#xff1a;
依次从左到右#xff0c;每次收集并删除所有的叶子节点重复如上过程直到整棵树为空
示例:
输入: [1,2,3,4,5]1/ \2 3/ \ 4 5 输出: [[4,5,3],[2],[1]…
文章目录1. 题目2. 解题1. 题目
给你一棵二叉树请按以下要求的顺序收集它的全部节点
依次从左到右每次收集并删除所有的叶子节点重复如上过程直到整棵树为空
示例:
输入: [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 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
类似题目LeetCode 156. 上下翻转二叉树DFS*
先自底向上翻转二叉树把子节点的 left指向父节点同时记录父节点有多少个子节点0,1,2,把叶子节点加入队列开始BFS出队一个就把该节点的 left 原来的父节点的子节点计数 -1当节点的子节点计数为0时它就变成了叶子节点可以入队了
class Solution {vectorvectorint ans;queueTreeNode* q;unordered_mapTreeNode*, int map;//父节点底下挂着几个子节点
public:vectorvectorint findLeaves(TreeNode* root) {reverse(root);//上下翻转二叉树while(!q.empty()){int size q.size(), i 0;vectorint lv(size);while(size--){TreeNode *cur q.front();q.pop();map[cur-left]--;//原父节点的子节点计数-1lv[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
上面做法遍历了2次树更简单的做法按照树的高度2侧子树的最大高度 1自己来分组
class Solution {vectorvectorint ans;
public:vectorvectorint 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 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
