※ 引述《dont (dont)》之銘言：
: 1110. Delete Nodes And Return Forest
: ## 思路
: DFS掃整個Tree
: 如果node沒有parent且不在to_delete就加到res
: ## Complexity
: Time, Space: O(N)
: ## Code
: ```python
: class Solution:
: def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) ->
: List[TreeNode]:
: to_delete = set(to_delete)
: res = []
: def dfs(node, has_parent):
: if not node:
: return
: if node.val not in to_delete and has_parent is False:
: res.append(node)
: has_parent = False if node.val in to_delete else True
: if node.left:
: dfs(node.left, has_parent)
: if node.left.val in to_delete:
: node.left = None
: if node.right:
: dfs(node.right, has_parent)
: if node.right.val in to_delete:
: node.right = None
: dfs(root, False)
: return res
: ```
思路:
找到to_delete的值
找到且有left or right就加到result
Python Code:
class Solution:
def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) ->
List[TreeNode]:
res = []
def dfs(root, is_root):
if not root:
return None
root_deleted = root.val in to_delete
if is_root and not root_deleted:
res.append(root)
root.left = dfs(root.left, root_deleted)
root.right = dfs(root.right, root_deleted)
return None if root_deleted else root
dfs(root, True)
return res