南阳市网站建设,青岛网站定做,空间网架,好看的模板来源#xff1a;力扣#xff08;LeetCode#xff09;
描述#xff1a;
给出二叉树的根节点 root#xff0c;树上每个节点都有一个不同的值。
如果节点值在 to_delete 中出现#xff0c;我们就把该节点从树上删去#xff0c;最后得到一个森林#xff08;一些不相交的…来源力扣LeetCode
描述
给出二叉树的根节点 root树上每个节点都有一个不同的值。
如果节点值在 to_delete 中出现我们就把该节点从树上删去最后得到一个森林一些不相交的树构成的集合。
返回森林中的每棵树。你可以按任意顺序组织答案。
示例 1
输入root [1,2,3,4,5,6,7], to_delete [3,5]
输出[[1,2,null,4],[6],[7]]示例 2
输入root [1,2,4,null,3], to_delete [3]
输出[[1,2,4]]提示
树中的节点数最大为 1000。每个节点都有一个介于 1 到 1000 之间的值且各不相同。to_delete.length 1000to_delete 包含一些从 1 到 1000、各不相同的值。
方法深度优先搜索
思路
题目给定一棵树 root树的每个节点都有一个各不相同的值。并且给定一个数组 to_delete包含需要删除的节点值。返回删除所有的 to_delete 中的节点后剩余的树的集合。
可以利用深度优先搜索来遍历每一个节点定义函数 dfs输入是参数是某个节点 node 和这个节点是否为潜在的新的根节点 is_root。函数中首先判断这个节点是否要被删除如果是那么它的两个子节点如果有的话便成为了潜在的根节点。如果这个节点的值不在 to_delete 中并且 is_root 为 true那么这个节点便成为了一个新的根节点需要把它放入结果数组中。同时也要对它的两个子节点进行同样的操作。dfs 的返回值为更新后的 node。
对根节点调用一次 dfs返回新的根节点数组即可。
代码
class Solution {
public:vectorTreeNode* delNodes(TreeNode* root, vectorint to_delete) {unordered_setint to_delete_set(to_delete.begin(), to_delete.end());vectorTreeNode * roots;functionTreeNode *(TreeNode *, bool) dfs [](TreeNode* node, bool is_root) - TreeNode * {if (node nullptr) {return nullptr;}bool deleted to_delete_set.count(node-val) ? true : false;node-left dfs(node-left, deleted);node-right dfs(node-right, deleted);if (deleted) {return nullptr;} else {if (is_root) {roots.emplace_back(node);}return node;}};dfs(root, true);return roots;}
};执行用时16ms, 在所有 C 提交中击败了92.74%的用户 内存消耗24.6 MB, 在所有 C 提交中击败了77.82%的用户 复杂度分析 时间复杂度O(n)其中 n 是树的节点数。 空间复杂度O(n)其中 n 是树的节点数。 authorLeetCode-Solution
