LeetCode 1110. 删点成林(二叉树递归)
发布日期:2021-07-01 03:25:12
浏览次数:2
分类:技术文章
本文共 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
关注你微信了!
[***.104.42.241]2024年05月03日 06时26分17秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Unix环境变量--线程基础
2019-05-02
Unix环境变量--缓冲区
2019-05-02
Unix环境变量--POSIX异步I/O
2019-05-02
tinyhttpd源码学习1
2019-05-02
Plus One
2019-05-02
Linux内核完全剖析0.12(一)
2019-05-02
Sum Root to Leaf Numbers
2019-05-02
Reverse Linked List II
2019-05-02
涨姿势:为啥MySQL官方不推荐使用uuid或者雪花id作为主键?
2019-05-02
一个小小的签到功能,到底用MySQL还是Redis?
2019-05-02
36岁退休!阿里 P8 六年实现“财务自由”,裸辞环游世界!
2019-05-02
QQ号终于能修改了?
2019-05-02
1.3 万亿条数据查询,如何做到毫秒级响应?
2019-05-02
高赞回答:为什么高级程序员不必担心自己的技术过时?
2019-05-02
支持 Dubbo 接口文档生成的工具
2019-05-02
SpringBoot集成WebSocket,实现后台向前端推送信息
2019-05-02
基于SpringBoot实现单点登录系统
2019-05-02
优秀程序员早就学会用“状态模式”代替if-else了
2019-05-02
Windows 10将预装Windows Terminal
2019-05-02
非常强悍的 RabbitMQ 总结,写得真好!
2019-05-02