ข้อ 42 · LC450 Delete Node in a BST (ลบโหนดใน BST) 🟡

# LeetCode ให้ class นี้มาให้แล้ว ที่เขียนไว้ตรงนี้เพื่อให้บล็อกนี้รันได้เองทั้งก้อน
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


# class TreeNode:
#     def __init__(self, val=0, left=None, right=None): ...

def delete_node(root, key):
    if not root:
        return None                      # ต้นไม้ว่าง ไม่มีอะไรให้ลบ

    if key < root.val:
        root.left = delete_node(root.left, key)   # key อยู่ฝั่งซ้าย
    elif key > root.val:
        root.right = delete_node(root.right, key) # key อยู่ฝั่งขวา
    else:
        # เจอ node ที่จะลบแล้ว แยก 3 กรณี
        if not root.left:
            return root.right            # ไม่มีลูกซ้าย ยกลูกขวาขึ้นมาแทน
        if not root.right:
            return root.left             # ไม่มีลูกขวา ยกลูกซ้ายขึ้นมาแทน

        # กรณีมีลูกสองตัว หาตัวที่น้อยสุดในฝั่งขวา (successor)
        succ = root.right
        while succ.left:
            succ = succ.left
        root.val = succ.val              # เอาค่า successor มาแทนค่าปัจจุบัน
        # แล้วลบ successor ออกจาก subtree ขวา
        root.right = delete_node(root.right, succ.val)

    return root

def inorder(node):
    """ไล่อ่าน BST แบบ in-order จะได้ค่าเรียงจากน้อยไปมากเสมอ"""
    if node is None:
        return []
    return inorder(node.left) + [node.val] + inorder(node.right)


# BST [5, 3, 6, 2, 4, null, 7]
root = TreeNode(5, TreeNode(3, TreeNode(2), TreeNode(4)), TreeNode(6, None, TreeNode(7)))
print(inorder(root))
root = delete_node(root, 3)          # ลบ 3 ซึ่งมีลูกสองข้าง
print(inorder(root))