Java,Python,C++,JavaScipt Easy Solution
Intuition\nTo solve this problem, we need to traverse the binary tree and handle the deletion of nodes specified in the to_delete list. We\'ll perform this trav
# Intuition\nTo solve this problem, we need to traverse the binary tree and handle the deletion of nodes specified in the to_delete list. We\'ll perform this traversal using a Depth-First Search (DFS) approach and keep track of the roots of the resulting trees in the forest. Here\'s a step-by-step approach:\n\nTraverse the Tree: Use DFS to traverse the tree.\nDelete Nodes: When a node is found in to_delete, it needs to be removed, and its children (if any) become new roots of separate trees.\nTrack Roots: Keep a list to store the roots of all trees in the resulting forest.\n\n# Explanation\nExplanation:\n1.TreeNode Definition: A class to define the structure of a tree node.\n2.delNodes Function:\n-Input Parameters: The root of the tree and the list of nodes to delete.\n-DFS Traversal: A nested dfs function to recursively traverse the tree. If the node is a root and not marked for deletion, it gets added to the forest list.\n-Deletion Handling: If the current node is in the to_delete set, it returns None, effectively deleting the node, and its children become new roots.\n3.Example Usage:\n-Constructs the example tree and calls delNodes with it.\n-Uses print_tree function to print the forest of trees in level order for easy verification.\n\nThis code successfully implements the solution and handles the deletion of nodes as specified.\n\n# Complexity\n- Time Complexity:O(n)\nEach node is visited once during the DFS traversal.\n\n- Space Complexity:O(n)\nThe recursion stack in the worst case takes O(h) space, where h is the height of the tree, and can be O(n) in the worst case.Additional space for storing the to_delete set and the resulting forest list is O(n).\n\n# Code\n```JAVA []\nclass Solution {\n        List<TreeNode> ans = new ArrayList();\n    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {\n        if(root == null || to_delete.length == 0)\n            return ans;\n        // if nothing to delete\n        if(to_delete.length == 0){\n            ans.add(root);\n            return ans;\n        }\n        \n        Deque<TreeNode[]> q = new ArrayDeque(); // curr, parent\n        Set<Integer> set = new HashSet();\n        for(int i : to_delete){\n            set.add(i);\n        }\n        // if root is not required to be deleted\n        if(!set.contains(root.val))\n            ans.add(root);\n            \n        q.add(new TreeNode[]{root,null});\n        util(q, set);\n        return ans;\n    }\n    \n    void util(Deque<TreeNode[]> q, Set<Integer> set){\n        while(!q.isEmpty()){\n            TreeNode[] curr = q.poll();\n            TreeNode node = curr[0];\n            TreeNode parent = curr[1];\n            \n            if(!set.contains(node.val)){ // just iterate with childrens\n                if(node.left != null)\n                    q.add(new TreeNode[]{node.left, node});\n                if(node.right != null)\n                    q.add(new TreeNode[]{node.right, node});\n            }else{ // if need to be deleted\n                // if curr is t be deleted, both left & right are part of answer.\n                if(node.left != null){\n                    if(!set.contains(node.left.val)){\n                        ans.add(node.left);\n                    }\n                    q.add(new TreeNode[]{node.left, node});\n                }\n                if(node.right != null){\n                    if(!set.contains(node.right.val)){\n                        ans.add(node.right);\n                    }\n                    q.add(new TreeNode[]{node.right, node});\n                }\n                \n                if(parent != null){\n                    if(parent.left == node){\n                        parent.left = null;\n                    }else{\n                        parent.right = null;\n                    }\n                }\n            }\n        }\n    }\n}\n```\n```Python []\nclass Solution(object):\n    def delNodes(self, root, to_delete):\n        to_delete = set(to_delete)\n        res = []\n        def walk(root, parent_exist):\n            if root is None:\n                return None\n            if root.val in to_delete:\n                root.left = walk(root.left, parent_exist=False)\n                root.right = walk(root.right, parent_exist=False)\n                return None\n            else:\n                if not parent_exist:\n                    res.append(root)\n                root.left = walk(root.left, parent_exist=True)\n                root.right = walk(root.right, parent_exist=True)\n                return root\n        walk(root, parent_exist=False)\n        return res\n\n```\n```C++ []\nclass Solution {\npublic:\n    \n    vector<TreeNode*> res;\n    set<int> dp;\n    \n    void util (TreeNode* &root)\n    {\n        if(root!=NULL)\n        {\n            util(root->left);\n            util(root->right);\n            if(dp.find(root->val)!=dp.end())\n            {\n                if(root->left)  res.push_back(root->left);\n                if(root->right) res.push_back(root->right);\n                root=NULL;\n\t\t\t\tdelete root;\n            }\n        }\n    }\n    \n    vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {\n\t\n        for(int i=0;i<to_delete.size();i++)\n            dp.insert(to_delete[i]);\n        util(root);\n        if(root)\n            res.push_back(root);\n        return res;\n    }\n};\n```\n```JavaScript []\n/**\n * @param {TreeNode} root\n * @param {number[]} to_delete\n * @return {TreeNode[]}\n */\nvar delNodes = function(root, to_delete) {\n    let roots = [];\n    let helper = function(root, isRoot) {\n        if (!root) return null;\n        let shouldDelete = to_delete.includes(root.val);\n        if (isRoot && !shouldDelete) roots.push(root);\n        root.left = helper(root.left, shouldDelete);\n        root.right = helper(root.right, shouldDelete);\n        return shouldDelete?null:root;\n    }\n    helper(root, true);\n    return roots;\n};\n```\nHope this is helpful!\n
['C++', 'Java', 'Python3', 'JavaScript']