Keshawn_lu's Blog

Leetcode 1110. 删点成林

深度优先搜索
字数统计: 587阅读时长: 2 min
2023/05/30 Share

题目简介：

给出二叉树的根节点 root，树上每个节点都有一个不同的值。

如果节点值在 to_delete 中出现，我们就把该节点从树上删去，最后得到一个森林（一些不相交的树构成的集合）。

返回森林中的每棵树。你可以按任意顺序组织答案。

示例 1：

screen-shot-2019-07-01-at-53836-pm

1
2
输入：root = [1,2,3,4,5,6,7], to_delete = [3,5]
输出：[[1,2,null,4],[6],[7]]

提示：

  • 中的节点数最大为 1000。
  • 每个节点都有一个介于 1 到 1000 之间的值，且各不相同。
  • to_delete.length <= 1000
  • to_delete 包含一些从 1 到 1000、各不相同的值。

思路：

首先将需要被删除的结点加入哈希表中

然后进行深搜solve(root, flag)，flag = 1表示这是一个新的root结点，需要被加入res中。

若遍历到的结点需要被删除，则其左右结点就会形成新的root结点。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:

    unordered_map<int, int> del;
    vector<TreeNode*> res;

    TreeNode* solve(TreeNode* root, int flag){

        if(!root)
            return nullptr;

        if(del[root->val] == 1){

            if(root->left)
                solve(root->left, 1);
            
            if(root->right)
                solve(root->right, 1);
            
            return nullptr; //说明需要被删除
        }

        if(flag == 1)
            res.push_back(root);

        if(!solve(root->left, 0))
            root->left = nullptr;
 
        if(!solve(root->right, 0))
            root->right = nullptr;
        
        return root;
    }

    vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
        
        for(auto& num : to_delete)
            del[num] = 1;

        solve(root, 1);

        return res;
    }
};

写法二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:

    unordered_map<int, int> del;
    vector<TreeNode*> res;

    void solve(TreeNode*& root, int flag) { //指针的引用

        if (!root)
            return;

        if (del[root->val] == 1) {

            solve(root->left, 1);
            solve(root->right, 1);

            root = nullptr; // 将父节点指向要删除节点的指针置为空
            return;
        }

        if (flag == 1)
            res.push_back(root);

        solve(root->left, 0);
        solve(root->right, 0);
    }

    vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
        
        for(auto& num : to_delete)
            del[num] = 1;

        solve(root, 1);

        return res;
    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网