Simple Java Simple Solution | HashSet | Beats 100% | Please UPVOTE
Intuition\nThe problem involves deleting specific nodes from a binary tree based on a given set of values to delete (to_delete). The intuition behind the soluti
# Intuition\nThe problem involves deleting specific nodes from a binary tree based on a given set of values to delete (`to_delete`). The intuition behind the solution is to perform a post-order traversal of the tree while identifying and deleting nodes as necessary.\n\n# Approach\nThe code follows these steps:\n\n1. Initialize a HashSet `set` to store the values to be deleted efficiently.\n2. Create an `ArrayList<TreeNode>` called `list` to store the result, initially empty.\n3. Define a recursive function `preorder` that traverses the binary tree in post-order. The function takes the current node `root`, the `set`, the `list` of results, and the parent node `parent`.\n   - If `root` is `null`, return the current `list`.\n   - Recursively call `preorder` on the left subtree and the right subtree.\n   - Check if the value of the current node `root.val` is in the `set`. If it is, the node needs to be deleted:\n     - Add its left and right children to the `list` if they exist and are not in the `set`.\n     - If the `parent` exists, update its left or right child to `null` based on the current node.\n   - Return the updated `list`.\n4. In the `delNodes` function, populate the `set` with the values to delete.\n5. Start the traversal with the `preorder` function, passing the root node, `set`, and an empty `list`.\n6. If the root node\'s value is not in the `set`, add it to the `list`.\n7. Return the final `list` containing the root nodes of the remaining subtrees after deleting the specified nodes.\n\n# Complexity\n- Time complexity: O(N) where N is the number of nodes in the binary tree. This is because the code performs a post-order traversal of the tree, visiting each node once.\n- Space complexity: O(H) in the worst case, where H is the height of the binary tree. This space is used for the recursive call stack. In a balanced tree, H is O(log N), but in the worst case (skewed tree), H can be O(N).\n\n\n# Code\n```\n/**\n * Definition for a binary tree node.\n * public class TreeNode {\n *     int val;\n *     TreeNode left;\n *     TreeNode right;\n *     TreeNode() {}\n *     TreeNode(int val) { this.val = val; }\n *     TreeNode(int val, TreeNode left, TreeNode right) {\n *         this.val = val;\n *         this.left = left;\n *         this.right = right;\n *     }\n * }\n */\nclass Solution {\n    public static ArrayList<TreeNode> preorder(TreeNode root, HashSet<Integer> set, ArrayList<TreeNode> list, TreeNode parent){\n        if(root == null) return list;\n        //System.out.println(root.val);\n        list = preorder(root.left, set, list, root);\n        list = preorder(root.right, set, list, root);\n        if(set.contains(root.val)){\n            System.out.println(root.val);\n            //list.add(root);\n            if(root.left!=null && !set.contains(root.left.val)) {\n                list.add(root.left);\n                root.left = null;\n            }\n            if(root.right!=null && !set.contains(root.right.val)) {\n                list.add(root.right);\n                root.right = null;\n            }\n            if(parent!=null){\n                if(parent.left!=null && parent.left.val == root.val){\n                    parent.left = null;\n                }\n                if(parent.right!=null && parent.right.val == root.val){\n                    parent.right = null;\n                }\n            }\n            //root = null;\n            //System.out.println(root.val);\n        }\n        \n        return list;\n\n    }\n    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {\n        HashSet<Integer> set = new HashSet<>();\n        for(int i=0; i<to_delete.length; i++){\n            set.add(to_delete[i]);\n        }\n        ArrayList<TreeNode> list = new ArrayList<TreeNode>();\n        list = preorder(root, set, list, null);\n        if(!set.contains(root.val)){\n            list.add(root);\n        }\n        \n        return list;\n        \n    }\n}\n```
['Java']