LeetCode 1110. 删点成林(二叉树递归)
发布日期:2021-07-01 03:25:12
浏览次数:3
分类:技术文章
本文共 1537 字,大约阅读时间需要 5 分钟。
1. 题目
给出二叉树的根节点 root,树上每个节点都有一个不同的值。
如果节点值在 to_delete 中出现,我们就把该节点从树上删去,最后得到一个森林(一些不相交的树构成的集合)。
返回森林中的每棵树。你可以按任意顺序组织答案。
示例:
输入:root = [1,2,3,4,5,6,7], to_delete = [3,5]输出:[[1,2,null,4],[6],[7]] 提示:树中的节点数最大为 1000。每个节点都有一个介于 1 到 1000 之间的值,且各不相同。to_delete.length <= 1000to_delete 包含一些从 1 到 1000、各不相同的值。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/delete-nodes-and-return-forest 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
2. 解题
- 要删除的放入哈希表,方便快速查找
- 递归遍历,记录父节点,和左右方向
- 如果要删除,断开父节点,子节点,遍历子节点
- 不删除,且父节点为空,加入答案
class Solution { unordered_set s; vectorans;public: vector delNodes(TreeNode* root, vector & to_delete) { if(!root) return { }; for(int del : to_delete) s.insert(del);//哈希快速查找 order(root, NULL, 0); return ans; } void order(TreeNode* root, TreeNode* father, int dir) { //参数,当前节点,其父节点,是父节点的左节点还是右节点 if(!root) return; if(s.count(root->val))//root需要删除 { if(father)//要删除的节点有父节点 { if(dir==0)//是左边过来的 father->left = NULL;//断开与父节点的链接 else father->right = NULL; } TreeNode *l = root->left, *r = root->right;//当前节点的左右子节点 root->left = NULL;//断开子的链接 root->right = NULL;//断开子的链接 order(l, NULL, 0);//遍历左子,其父节点断开了,为空,第三个参数随意 order(r, NULL, 0);//遍历右子 } else//root不用删除 { if(!father)//如果没有父节点了,新的树根,加入答案 ans.push_back(root); order(root->left, root, 0);//遍历左子,第三个参数0表示左 order(root->right, root, 1);//遍历右子,第三个参数1表示右 } }};
转载地址:https://michael.blog.csdn.net/article/details/105968905 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
很好
[***.229.124.182]2024年04月17日 16时37分31秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
剑指offer:第一个只出现一次的字
2019-05-03
剑指offer:数组中的逆序对(java)
2019-05-03
剑指offer:两个链表的第一个公共结点(java)
2019-05-03
剑指offer:数字在排序数组中出现的次数(java)
2019-05-03
实时开发框架Meteor API解读系列<二>Core
2019-05-03
实时开发框架Meteor 实际应用系列<一>---文件的上传和下载
2019-05-03
实时开发框架Meteor API解读系列<四>Server connections
2019-05-03
实时开发框架Meteor API解读系列<五>Session
2019-05-03
实时开发框架Meteor API解读系列<六> DDP
2019-05-03
实时开发框架Meteor 实际应用系列<一>---文件的上传和下载[补充]
2019-05-03
实时开发框架Meteor API解读系列<七> Collection --01
2019-05-03
实时开发框架Meteor API解读系列<八> Timers
2019-05-03
ubuntu sublime无法输入中文问题
2019-05-03
启用fcitx-qimpanel面板程序
2019-05-03
浅谈Q的基本实现
2019-05-03
python os模块
2019-05-03
iOS8 Push Notifications
2019-05-03
iOS8 PUSH解决方法
2019-05-03