DFS adds Nodes without parents
Intuition\n Describe your first thoughts on how to solve this problem. \nThere are some Tree nodes to remove; after the removal, add the tree nodes without pare
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThere are some Tree nodes to remove; after the removal, add the tree nodes without parent node to answer list.\n\n2 approaches are given.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. For the constaint `Each node has a distinct value between 1 and 1000.` use `bitset<10001> rmv=0` to replace a hash table.\n2. Use a loop to set `rmv[x]=1` for x in `to_delete`\n3. define a recursive function `void dfs(TreeNode* root, TreeNode* parent, bool isLeft)` to deal with the removal.\n4. If `rmv[root->val]` the root should be removed;  judge whether it is a left or a right child, remove its connection to parent; then proceed\n```\ndfs(root->left, NULL, 1);\ndfs(root->right, NULL, 0);\ndelete root;\n```\n5. Otherwise, root should be kept; if it has no parent, add it to answering list `ans`. Then proceed `dfs(root->left, root, 1);\n            dfs(root->right, root, 0);`\n6. Call `dfs(root, NULL, 1)`\n7. Return `ans`\n8. A simplified version `TreeNode* dfs(TreeNode* root, TreeNode* parent) ` is given which simplifies the function & removes the parameter `isLeft`.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n $$O(n)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n $$O(n+|to\\_delete|)$$\n# Code\n```\nclass Solution {\npublic:\n    const static int N = 1001;\n    bitset<N> rmv = 0;\n    vector<TreeNode*> ans;\n\n    void dfs(TreeNode* root, TreeNode* parent, bool isLeft) {\n        if (!root) return;\n        if (rmv[root->val]) {\n            if (parent) {\n                if (isLeft) parent->left = NULL;\n                else parent->right = NULL;\n            }\n            dfs(root->left, NULL, 1);\n            dfs(root->right, NULL, 0);\n            delete root;  // Free the memory of the deleted node\n        } \n        else {\n            if (!parent) \n                ans.push_back(root);\n\n            dfs(root->left, root, 1);\n            dfs(root->right, root, 0);\n        }\n    }\n\n    vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {\n        for (int x : to_delete) \n            rmv[x] = 1;\n        dfs(root, NULL, 1);\n        return ans;\n    }\n};\n\n```\n# A simple recursive dfs\n```\n    TreeNode* dfs(TreeNode* root, TreeNode* parent) {\n        if (!root) return NULL;\n        TreeNode* kept=rmv[root->val]?NULL:root;\n        if (!parent && kept) ans.push_back(root);\n        root->left=dfs(root->left, kept);\n        root->right=dfs(root->right, kept);\n        if (!kept) {\n            delete root; \n            return NULL;\n        }\n        return root;  \n    }\n```
['Array', 'Bit Manipulation', 'Depth-First Search', 'Binary Tree', 'C++']