🌳Trees to Forest🌳||Fastest (97.28%)🚀🚀||Easiest🤩🤩||DFS🧐🧐
\n\n# Intuition\nThe problem involves deleting specified nodes from a binary tree and then returning the roots of the remaining disjoint subtrees, forming a for
![image.png](https://assets.leetcode.com/users/images/7157f425-c7bf-4db9-a03b-4e837684555a_1721182861.6392112.png)\n\n# Intuition\nThe problem involves deleting specified nodes from a binary tree and then returning the roots of the remaining disjoint subtrees, forming a forest. The challenge is to effectively traverse the tree, identify nodes to be deleted, and manage the separation of subtrees. The idea is to use a recursive approach to traverse the tree while keeping track of nodes that need to be deleted. By recursively checking each node, we can decide if a node should be removed and, if so, ensure its children become new roots of the resulting forest. This way, the tree is split correctly, and the resulting forest roots are collected as we traverse.\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nThe solution uses a recursive helper function to traverse the binary tree. The function processes each node, checking if its value is in the set of values to be deleted. If a node is to be deleted, its children are added to the result list if they exist, effectively making them new roots of the subtrees. The function then returns null to indicate that the current node is removed. If a node is not to be deleted, the function continues traversing its children. After the traversal, the initial root is checked separately to ensure it is added to the result if it wasn\'t deleted. This approach ensures that the tree is correctly transformed into a forest, and all the new roots are collected in the result list.\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(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    private TreeNode deleteHelper(TreeNode root, Set<Integer> toDelete, List<TreeNode> result) {\n        if (root == null) {\n            return null;\n        }\n\n        root.left = deleteHelper(root.left, toDelete, result);\n        root.right = deleteHelper(root.right, toDelete, result);\n\n        if (toDelete.contains(root.val)) {\n            if (root.left != null) {\n                result.add(root.left);\n            }\n            if (root.right != null) {\n                result.add(root.right);\n            }\n            return null;\n        } else {\n            return root;\n        }\n    }\n\n    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {\n        List<TreeNode> result = new ArrayList<>();\n        Set<Integer> toDelete = new HashSet<>();\n\n        for (int num : to_delete) {\n            toDelete.add(num);\n        }\n\n        deleteHelper(root, toDelete, result);\n\n        if (!toDelete.contains(root.val)) {\n            result.add(root);\n        }\n\n        return result;\n    }\n}\n```\n![Screenshot 2024-06-12 075242.png](https://assets.leetcode.com/users/images/fac4b468-58f7-42e1-833a-311ca910c8b0_1721182907.1716607.png)\n
['Array', 'Tree', 'Depth-First Search', 'Binary Tree', 'Java']