1110. 删点成林

删点成林

原题：

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

解题方法：

解法一：

class Solution {
public:
    vector<TreeNode*> res;
    vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
        Delete(root,to_delete);
        if(!Contain(root,to_delete)&&root) res.push_back(root);
        return res;
    }

    void Delete(TreeNode*& node,vector<int>& to_delete)  //因为要在原树上做更改，因此要用&
    {
        if(!node) return;    
        Delete(node->left,to_delete);
        Delete(node->right,to_delete);
        if(Contain(node,to_delete))
        {
            if(node->left) res.push_back(node->left);  //由于是后序遍历就不需要再判断左子树右子树是否为要删除的点了
            if(node->right) res.push_back(node->right);
            node=nullptr;
        }
    }

    bool Contain(TreeNode* node,vector<int> to_delete)
    {
        if(!node) return false;
        for(int i=0;i<to_delete.size();i++)
        {
            if(node->val==to_delete[i])
            {
                return true;
            }
        }
        return false;
    }
};

解法二（使用无序集改进）：

class Solution {
public:
    vector<TreeNode*> res;
    vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
        unordered_set<int> delSet(to_delete.begin(), to_delete.end());
        Delete(root,delSet);
        if(root&&!delSet.count(root->val)) res.push_back(root);
        return res;
    }

    void Delete(TreeNode*& node,unordered_set<int> delSet)  //因为要在原树上做更改，因此要用&
    {
        if(!node) return;    
        Delete(node->left,delSet);
        Delete(node->right,delSet);
        if(delSet.count(node->val))
        {
            if(node->left) res.push_back(node->left);  //由于是后序遍历就不需要再判断左子树右子树是否为要删除的点了
            if(node->right) res.push_back(node->right);
            node=nullptr;
        }

    }

};

做题小结：

针对解法一：

1. 使用后序遍历，当遇到要删除的点时就可以直接删除，不用考虑是否在这个节点下是否还有需要删除的点
2. root在子函数中要使用&才能改变它的值
3. 可以使用unordered_set来降低检索值的时间复杂度，详情请见解法二
4. 之前卡在处理最顶上的节点，其实先不考虑，最后再来单独处理就好了