450. Delete Node in a BST

Medium

Description

給定一棵 BST 的根節點和一個要刪除的值 key，刪除 BST 中該值對應的節點並回傳根節點。如果 key 不存在則不做任何操作。

Example:

Input: root = [5,3,6,2,4,null,7], key = 3 Output: [5,4,6,2,null,null,7]

Intuition#

找到目標節點後，分三種情況處理：無子節點直接刪除、有一個子節點用子節點替代、有兩個子節點用後繼節點替代。

先利用 BST 性質找到目標節點
刪除節點的三種情況：
1. 葉子節點：直接刪除
2. 只有一個子節點：用子節點替代
3. 有兩個子節點：找右子樹的最小值（中序後繼）替代，再刪除該後繼節點

Approaches#

⭐ 1: Recursive#

概念: 遞迴搜尋目標節點，找到後根據子節點情況處理
時間複雜度: O(h)，h 為樹高
空間複雜度: O(h)，遞迴堆疊深度

class Solution {
    fun deleteNode(root: TreeNode?, key: Int): TreeNode? {
        if (root == null) return null
        when {
            key < root.`val` -> root.left = deleteNode(root.left, key)
            key > root.`val` -> root.right = deleteNode(root.right, key)
            else -> {
                // 找到目標節點
                if (root.left == null) return root.right
                if (root.right == null) return root.left
                // 有兩個子節點：找右子樹最小值
                var successor = root.right!!
                while (successor.left != null) {
                    successor = successor.left!!
                }
                root.`val` = successor.`val`
                root.right = deleteNode(root.right, successor.`val`)
            }
        }
        return root
    }
}

2: Iterative#

概念: 迭代找到目標節點及其父節點，再處理刪除邏輯
時間複雜度: O(h)
空間複雜度: O(1)

class Solution {
    fun deleteNode(root: TreeNode?, key: Int): TreeNode? {
        var parent: TreeNode? = null
        var curr = root
        // 找到目標節點
        while (curr != null && curr.`val` != key) {
            parent = curr
            curr = if (key < curr.`val`) curr.left else curr.right
        }
        if (curr == null) return root
        // 處理刪除
        val replacement = when {
            curr.left == null -> curr.right
            curr.right == null -> curr.left
            else -> {
                // 找右子樹最小值
                var succParent = curr
                var succ = curr.right!!
                while (succ.left != null) {
                    succParent = succ
                    succ = succ.left!!
                }
                if (succParent != curr) {
                    succParent.left = succ.right
                    succ.right = curr.right
                }
                succ.left = curr.left
                succ
            }
        }
        return when {
            parent == null -> replacement
            parent.left == curr -> { parent.left = replacement; root }
            else -> { parent.right = replacement; root }
        }
    }
}

🔑 Takeaways#

Pattern: BST 刪除 — 三種情況分別處理，核心是用中序後繼替代
關鍵技巧: 刪除有兩個子節點的節點時，找右子樹最小值（一路向左走到底）作為替代值是標準做法