[Python] Recursive Solution with Backtracking
The basic idea is to traverse the binary tree recursively in preorder. At each node we perform the following actions:\n1. If the current node\'s parent is marke
The basic idea is to traverse the binary tree recursively in preorder. At each node we perform the following actions:\n1. If the current node\'s parent is marked for deletion, but the current node is not, then the current node is the root of a tree.\n2. Visit the left and right subtrees. \n2. If a child node is marked for deletion, delete it.\n3. Report to the parent node whether the current node should be deleted. \n\nTime complexity: O(N)\nSpace complexity: O(d), d is the depth of the tree\n\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: TreeNode, to_delete: List[int]) -> List[TreeNode]:        \n        to_delete = set(to_delete)\n        roots = []\n        \n        def preorder(node, parent_deleted):\n            if not node:\n                return False\n            \n            self_deleted = node.val in to_delete\n            if parent_deleted and not self_deleted:\n                # If parent is deleted, but the current node is \n                # not, then the current node is the root of a tree.\n                roots.append(node)\n            \n            # Delete child depending on return value.\n            if preorder(node.left, self_deleted):\n                node.left = None\n            if preorder(node.right, self_deleted):\n                node.right = None\n                \n            # Report to the parent whether the current node should be deleted.\n            return self_deleted\n                \n        preorder(root, True)\n        return roots\n```
[]