Problem: 1110. Delete Nodes And Return Forest 删点成林

后序遍历整棵树，哈希表记录需要删除的node数字，参数需要包括父节点，以及属于左子树还是右子树的标记lr，若left非空则放入left，right非空放入right，若lr0左子树则父节点左子树置空，lr=1右子树则父节点右子树置空，若lr-1则根节点被删除

最后若根节点不需要被删除，还需要加入根节点

Code

/**
 * 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:
    vector<TreeNode*> ret;
    bool ch[1001];
    void dfs(TreeNode* root, TreeNode* par, int lr) {
        if(root == nullptr) return;
        dfs(root->left, root, 0);
        dfs(root->right, root, 1);
        if(ch[root->val] == true) {
            if(root->left != nullptr) {
                ret.push_back(root->left);
            }
            if(root->right != nullptr) {
                ret.push_back(root->right);
            }
            if(lr == 0) {
                par->left = nullptr;
            } else if(lr == 1) {
                par->right = nullptr;
            } else {
                root = nullptr;
            }
        }
    }
    vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
        memset( ch, 0, sizeof(ch) );
        for(int& i : to_delete) ch[i] = true;
        dfs(root, nullptr, -1);
        if(ch[root->val]==false) ret.push_back(root);
        return ret;
    }
};