Delete Nodes And Return Forest: ลบโหนดและคืน Forest ใน Binary Tree

โจทย์

กำหนด Binary Tree root และ array to_delete ลบโหนดที่ value อยู่ใน to_delete ทั้งหมดพร้อมกัน คืน roots ของ forest ที่เหลือ

ตัวอย่าง: Tree [1,2,3,4,5,6,7], to_delete=[3,5] → Forest roots: [1,6,7]

Original:          After delete 3,5:
    1                    1
   / \                  /
  2   3                2
 / \ / \              /
4  5 6  7            4

Forest roots: 1, 6, 7

อัลกอริทึม: Post-order DFS + Parent Info

DFS post-order เพื่อรู้ว่า child ถูกลบหรือไม่ ถ้าถูกลบ → child กลายเป็น root ใหม่ (ถ้าไม่ถูกลบ)

การติดตั้ง (Python Implementation)

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: TreeNode, to_delete: list[int]) -> list[TreeNode]:
        to_delete_set = set(to_delete)
        forest = []
        
        def dfs(node, is_root):
            if not node:
                return None
            
            # ตรวจสอบว่า node นี้ถูกลบหรือไม่
            deleted = node.val in to_delete_set
            
            # ถ้าไม่ถูกลบ และเป็น root (parent ถูกลบ หรือเป็น original root) → เพิ่มใน forest
            if not deleted and is_root:
                forest.append(node)
            
            # Recurse: child จะเป็น root ใหม่ถ้า parent ถูกลบ (deleted=True)
            node.left = dfs(node.left, deleted)
            node.right = dfs(node.right, deleted)
            
            # คืน None ถ้าถูกลบ, มิฉะนั้นคืน node
            return None if deleted else node
        
        dfs(root, True)
        return forest

# Helper
def build_tree(vals):
    if not vals:
        return None
    nodes = [TreeNode(v) if v is not None else None for v in vals]
    for i, node in enumerate(nodes):
        if node:
            li, ri = 2*i+1, 2*i+2
            if li < len(nodes):
                node.left = nodes[li]
            if ri < len(nodes):
                node.right = nodes[ri]
    return nodes[0]

def print_forest(forest):
    def inorder(node):
        if not node:
            return []
        return inorder(node.left) + [node.val] + inorder(node.right)
    for i, root in enumerate(forest):
        print(f"Tree {i}: {inorder(root)}")

# ทดสอบ
ob = Solution()
root = build_tree([1,2,3,4,5,6,7])
forest = ob.delNodes(root, [3,5])
print_forest(forest)
# Tree 0: [4, 2, 1]
# Tree 1: [6]
# Tree 2: [7]

Output

Tree 0: [4, 2, 1]
Tree 1: [6]
Tree 2: [7]

Complexity

• Time: O(n) - เยี่ยมทุกโหนด 1 ครั้ง
• Space: O(h + d) โดย h = height, d = len(to_delete) สำหรับ set และ recursion stack

สรุป

Delete Nodes And Return Forest ใช้ Post-order DFS พร้อม flag is_root บ่งบอกว่า child นี้ควรเป็น root ใหม่หรือไม่ (เมื่อ parent ถูกลบ) ใส่ forest เมื่อ not deleted and is_root

หากมีข้อสงสัย สามารถถามได้ในส่วนความคิดเห็นครับ