1110. Delete Nodes And Return Forest

O(n) time O(h + to_delete) space
判断是否需要删除需要hashtable
如果需要删除必须『真』删除，采用重新赋左右子的值的方法来删除
如果当前root需要删除，则把左右子树遍历删除后的结果尝试加入森林，所以需要后序遍历
如果当前root不需要删除，则update左右子之后返回即可（注意root并不一定是森林里的一棵树的根）

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
        for (int x : to_delete) {
            s.insert(x);
        }
        auto ret = del(root);
        if (ret) {
            res.push_back(ret);
        }
        return res;
    }

    TreeNode *del(TreeNode *root) {
        if (!root) return root;
        auto l = del(root->left), r = del(root->right);
        if (s.count(root->val)) {
            if (l) {
                res.push_back(l);
            }
            if (r) {
                res.push_back(r);
            }
            return nullptr;
        }
        root->left = l;
        root->right = r;
        return root;
    }

    vector<TreeNode *> res;
    unordered_set<int> s;
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
        for (int x : to_delete) {
            s.insert(x);
        }
        TreeNode dummy;
        dummy.left = root;
        s.insert(0);
        del(&dummy);
        return res;
    }

    TreeNode *del(TreeNode *root) {
        if (!root) return root;
        auto l = del(root->left), r = del(root->right);
        if (s.count(root->val)) {
            if (l) {
                res.push_back(l);
            }
            if (r) {
                res.push_back(r);
            }
            return nullptr;
        }
        root->left = l;
        root->right = r;
        return root;
    }

    vector<TreeNode *> res;
    unordered_set<int> s;
};