給定一棵 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
TIP
找到目標節點後，分三種情況處理：無子節點直接刪除、有一個子節點用子節點替代、有兩個子節點用後繼節點替代。
- 先利用 BST 性質找到目標節點
- 刪除節點的三種情況：
- 葉子節點：直接刪除
- 只有一個子節點：用子節點替代
- 有兩個子節點：找右子樹的最小值（中序後繼）替代，再刪除該後繼節點
Approaches
⭐ 1. Recursive — O(h) / O(h)
- Idea: 遞迴搜尋目標節點，找到後根據子節點情況處理
- Time:
O(h)，h 為樹高 - Space:
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)
- Idea: 迭代找到目標節點及其父節點，再處理刪除邏輯
- Time:
O(h) - Space:
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 刪除 — 三種情況分別處理，核心是用中序後繼替代
- Key trick: 刪除有兩個子節點的節點時，找右子樹最小值（一路向左走到底）作為替代值是標準做法