✅💯🔥14 LoC | Easiest Logic | Post order Traversal
Intuition\nThe problem requires deleting certain nodes from a binary tree and returning the remaining forest as a list of tree roots. The idea is to traverse po
# Intuition\nThe problem requires deleting certain nodes from a binary tree and returning the remaining forest as a list of tree roots. The idea is to traverse post order and manage the forest creation as nodes are deleted. When a node to be deleted is found, its children (if any) become new roots in the forest.\n\n# Approach\n1. Depth-First Search (DFS): Use DFS to traverse the tree.\n2. Check Deletion: At each node, check if it is in the to_delete list.\n    - If it is, add its children (if any) to the result list res as new roots.\n    - Return None for deleted nodes to disconnect them from their parent.\n3. Root Management: If the current node is not deleted and is a root (initially the given root or a new root after deletion), add it to the result list.\n4. Recursive Traversal: Recursively apply the above logic to left and right children.\n5. Return Result: The res list contains the roots of the remaining forest.\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# Definition for a binary tree node.\n# class TreeNode:\n#     def __init__(self, val=0, left=None, right=None):\n#         self.val = val\n#         self.left = left\n#         self.right = right\nclass Solution:\n    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n        res = []\n        to_delete = set(to_delete)\n        def dfs(node, is_root):\n            if not node:\n                return\n            node.left = dfs(node.left, False)\n            node.right = dfs(node.right, False)\n            if node.val in to_delete:\n                if node.left:\n                    res.append(node.left)\n                if node.right:\n                    res.append(node.right)\n                return \n            if is_root:\n                res.append(node)\n            return node\n        dfs(root, True)\n        return res\n```
['Python3']