# 1110. Delete Nodes And Return Forest

## :memo: Question

## :memo: 題意
* 給你一個 tree, 和一個 delete list, 求當我把想要刪除的節點都刪掉後, 請返回剩下的 tree.

## :memo: leetcode solution
* :medal: **思考一**: 一開始思考當我們走到 node 時，他是什麼狀況下我們會要把他放到答案裡，要考慮什麼
* 這個 node 會是 root 嗎？ 如果是 root 那我們要加到答案裡
* **判斷方式:**
* 這個 node 是否有 parent?
* 當前的 node 是否在 delete list 裡，如果是要怎麼跟下面的 child 說, 你沒有 parent?
* 這個 node 有 child 嗎？ 如果 child 是要被刪除的，那要把它刪除掉
* 

* :medal: **思考二**: 要想出這題要用 dfs or bfs

## :memo: my solution code(bfs)

class Solution:
    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:
        to_delete = set(to_delete)
        queue = collections.deque([(root, 0)])
        ans = []
        while queue:
            # if no parent we need to push it to ans and it's value not in delete
            root, has_parent = queue.popleft()
            # 思考一提到的判斷
            if root.val not in to_delete and not has_parent:
                ans.append(root)
            
            if root.left:
                queue.append((root.left, 0 if root.val in to_delete else 1))
                # 思考一提到的判斷
                if root.left.val in to_delete:
                    root.left = None

            if root.right:
                queue.append((root.right, 0 if root.val in to_delete else 1))
                # 思考一提到的判斷
                if root.right.val in to_delete:
                    root.right = None
        
        return ans
            

## :memo: my solution code(dfs)

class Solution:
    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:

        self.ans = []
        self.delete = set(to_delete)
        self.dfs(root, 0)
        return self.ans

    def dfs(self, node, has_parent):
        if not node:
            return
        # 思考一提到的判斷
        if node.val not in self.delete and not has_parent:
            self.ans.append(node)
        # 思考一提到的判斷
        next_node_has_parent = 1
        if node.val in self.delete:
            next_node_has_parent = 0

        self.dfs(node.left, next_node_has_parent)
        self.dfs(node.right, next_node_has_parent)
        
        # 思考一提到的判斷
        if node.left and node.left.val in self.delete:
            node.left = None
        if node.right and node.right.val in self.delete:
            node.right = None
            

## :memo: BigO
* 時間複雜度: O(n)。
* 空間複雜度: O(n)。