LC 1110 [M] Delete Nodes And Return Forest - ALawliet/algorithms GitHub Wiki

this question is testing how we pass values down through arguments and up through the return, can just use preorder

we are essentially "deleting" the node with the return value as the child notifies the parent up that it was deleted

and so if it arrives at a current child that is not to be deleted and that node has no parent (the parent was deleted), then it must be a root

parent (is_deleted)
=
child (is_root)`

and if child (not to_delete)
=
disjoint union tree

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:
        to_delete = set(to_delete) # faster lookup
        
        res = []
        def walk(root, parent):
            if root is None:
                return None
            
            # current node is to be deleted, so next node gets no parent
            # in order for node to be deleted, child notify parent up
            if root.val in to_delete:
                root.left = walk(root.left, False)
                root.right = walk(root.right, False)
                
                return None # child notify parent up that it was deleted, stop exploring
            else:
                # arrived at a node with no parent, this is a disjoint union of trees
                # node is removed and parent notify child down
                if not parent: # therefore root
                    res.append(root)
                    
                root.left = walk(root.left, True)
                root.right = walk(root.right, True)
                                 
                return root # child notify parent up that it exists and was not deleted, keep exploring
            
        walk(root, False)
        
        return res

class Solution:
    def delNodes(self, root, to_delete):
            to_delete = set(to_delete)
            res = []

            def preorder(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 = preorder(root.left, root_deleted)
                root.right = preorder(root.right, root_deleted)
                
                return None if root_deleted else root
            
            preorder(root, True)
            return res