力扣解法汇总1110. 删点成林

目录链接：

力扣编程题-解法汇总_分享 记录-CSDN博客

GitHub同步刷题项目：

GitHub - September26/java-algorithms: 算法题汇总，包含牛客，leetCode，lintCode等网站题目的解法和代码，以及完整的mode类，甚至链表代码生成工具都有提供。

原题链接：力扣

描述：

给出二叉树的根节点 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 <= 1000
• to_delete 包含一些从 1 到 1000、各不相同的值。

解题思路：

/**

* 思路：

* search方法的返回值决定是否要删除当前节点。

* true代表删除，false代表不删除。

* 递归方法中，首先对左右子节点进行递归遍历，如果返回的是删除当前节点，则把对应的左右节点设置为nullptr.

* 然后查找当前节点的val是否在set中，则需要把左右节点加入到list中。但是左右节点需要判空，如果为空，则说明此节点其实已经被删掉了，则也不需要加入到list中。

*/

代码：

1.  
   #include <iostream>
2.  
   #include <map>
3.  
   #include <list>
4.  
   #include <vector>
5.  
   #include <set>
6.  
   #include "Solution1110.h"
7.  
   #include "../model/TreeNode.h"
8.  
    
9.  
   bool search(vector<TreeNode *> &list, set<int> set, TreeNode *root)
10.  
    {
11.  
    if (root == nullptr)
12.  
    {
13.  
    return false;
14.  
    }
15.  
    if (search(list, set, root->left))
16.  
    {
17.  
    root->left = nullptr;
18.  
    }
19.  
    if (search(list, set, root->right))
20.  
    {
21.  
    root->right = nullptr;
22.  
    }
23.  
     
24.  
    if (set.find(root->val) != set.end())
25.  
    {
26.  
    if (root->left != nullptr)
27.  
    {
28.  
    list.push_back(root->left);
29.  
    }
30.  
    if (root->right != nullptr)
31.  
    {
32.  
    list.push_back(root->right);
33.  
    }
34.  
    return true;
35.  
    }
36.  
    return false;
37.  
    }
38.  
     
39.  
    /**
40.  
    * 思路：
41.  
    * search方法的返回值决定是否要删除当前节点。
42.  
    * true代表删除，false代表不删除。
43.  
    *
44.  
    *
45.  
    */
46.  
    vector<TreeNode *> Solution1110::delNodes(TreeNode *root, vector<int> &to_delete)
47.  
    {
48.  
    vector<TreeNode *> list;
49.  
    std::set<int> mySet;
50.  
    for (int i : to_delete)
51.  
    {
52.  
    mySet.insert(i);
53.  
    }
54.  
    if (!search(list, mySet, root))
55.  
    {
56.  
    list.push_back(root);
57.  
    }
58.  
    return list;
59.  
    }

这篇好文章是转载于：学新通技术网