題目描述:給定一棵二元搜尋樹的根節點 root 以及一個整數 key,請刪除樹中值為 key 的節點,並回傳更新後的樹根。若 key 不存在於樹中,則樹不變。刪除後必須保持 BST 的性質。
解題思路:刪除 BST 節點分三種情況處理:
nullptr。遞迴架構:先用 BST 二分性質往左或往右尋找目標節點,找到後套用上述三種情況的處理邏輯,並將修改後的子樹回傳給上層,完成鏈結更新。
時間複雜度:O(h) — h 為樹的高度。搜尋目標節點需 O(h) 時間;有兩個子節點時,尋找中序後繼也需 O(h) 時間;最終再遞迴刪除後繼節點同樣 O(h)。對於平衡 BST,h = O(log n);最壞情況(退化為鏈結串列)h = O(n)。
空間複雜度:O(h) — 遞迴呼叫棧深度等於樹的高度,平衡時為 O(log n),退化時為 O(n)。
1. If root is null, return null (key not found)
2. If key < root.val, recurse on left subtree: root.left = deleteNode(root.left, key)
3. If key > root.val, recurse on right subtree: root.right = deleteNode(root.right, key)
4. Else (key == root.val), node found:
a. If no left child, return root.right
b. If no right child, return root.left
c. Both children exist:
i. Find in-order successor: go right once, then left as far as possible
ii. Copy successor's value into root.val
iii. Delete successor from right subtree: root.right = deleteNode(root.right, successor.val)
5. Return root方法一:以中序前驅替代(predecessor-based) 有兩個子節點時,也可以選用左子樹中最右邊的節點(中序前驅,in-order predecessor)來替代。將被刪節點的值換成前驅值,再遞迴從左子樹中刪除前驅節點。效果與後繼法完全等價,時間複雜度同為 O(h),選擇哪種取決於個人偏好或是否需要維持特定的樹形平衡。
方法二:迭代實作 以迭代方式搜尋目標節點,同時記錄父節點與方向(左/右子節點)。找到節點後依三種情況處理,並直接修改父節點的指標。此法省去遞迴呼叫棧,空間複雜度降為 O(1)(不計樹本身),但程式碼較冗長,需要特別處理刪除根節點的邊界情況。時間複雜度仍為 O(h)。