Best/Easiest Java Solution🔥
Intuition\nThe problem is to remove specific nodes from a binary tree and return the roots of the remaining forest, which is a collection of disjoint trees. Whe
# Intuition\nThe problem is to remove specific nodes from a binary tree and return the roots of the remaining forest, which is a collection of disjoint trees. When a node is deleted, its children become new roots of separate trees, provided they are not deleted themselves. Thus, we need to traverse the tree, delete the specified nodes, and manage the resulting forest roots.\n# Approach\n1. **Convert to_delete List to Set:** This allows O(1) time complexity for checking if a node needs to be deleted.\n2. **Depth-First Search (DFS):** We traverse the tree using DFS. During the traversal:\nIf a node needs to be deleted, add its non-null children to the forest (as they become new roots if not deleted themselves).\nRemove the node by returning null.\nIf a node doesn\'t need to be deleted, return it as part of the tree.\n3. **Manage Forest:** After processing the root node, if it is not deleted, add it to the forest.\n# Complexity\n- Time complexity:\nO(N)\n\n- Space complexity:\nO(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 List<TreeNode> delNodes(TreeNode root, int[] to_delete) {\n        List<TreeNode> forest = new ArrayList<>();\n        Set<Integer> toDeleteSet = new HashSet<>();\n        \n        // Add all elements to delete to a set for faster lookup\n        for (int val : to_delete) {\n            toDeleteSet.add(val);\n        }\n        \n        // Helper function to handle the recursion\n        root = deleteNodes(root, toDeleteSet, forest);\n        \n        // If the root itself is not deleted, add it to the forest\n        if (root != null) {\n            forest.add(root);\n        }\n        \n        return forest;\n    }\n\n    private TreeNode deleteNodes(TreeNode node, Set<Integer> toDeleteSet, List<TreeNode> forest) {\n        if (node == null) {\n            return null;\n        }\n        \n        // Recursively delete nodes in the left and right subtrees\n        node.left = deleteNodes(node.left, toDeleteSet, forest);\n        node.right = deleteNodes(node.right, toDeleteSet, forest);\n        \n        // If the current node needs to be deleted\n        if (toDeleteSet.contains(node.val)) {\n            // Add the left and right children to the forest if they exist\n            if (node.left != null) {\n                forest.add(node.left);\n            }\n            if (node.right != null) {\n                forest.add(node.right);\n            }\n            return null; // Return null to delete the current node\n        }\n        \n        return node; // Return the current node if it is not deleted\n    }\n}\n```
['Java']