Contents

# 450. Delete Node in a BST

## 題目 :

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

``````1.Search for a node to remove.
2.If the node is found, delete the node.
``````
• Follow up: Can you solve it with time complexity O(height of tree)?

### Example :

Note

Example 1:

Input: root = [5,3,6,2,4,null,7], key = 3 Output: [5,4,6,2,null,null,7] Explanation: Given key to delete is 3. So we find the node with value 3 and delete it. One valid answer is [5,4,6,2,null,null,7], shown in the above BST. Please notice that another valid answer is [5,2,6,null,4,null,7] and it’s also accepted.

Example 2:

Input: root = [5,3,6,2,4,null,7], key = 0 Output: [5,3,6,2,4,null,7] Explanation: The tree does not contain a node with value = 0.

Example 3:

Input: root = [], key = 0 Output: []

#### 解題思路 :

• 這題是 BST 非常重要的 delete operation，總體來說就是 1.尋找 2.刪除
• 在搜尋的部分一樣是 if..else 分成左右兩邊的recursive code做成 O(log(n))的複雜度
• 在刪除的部分主要可以分成三種情況:
1. 該 node 的 right subtree 為 null
2. 該 node 的 left subtree 為 null
3. 該 node 的 right && left subtree 皆不為 null

• 第1種及第2種最簡單都是直接return不為null的另一邊
• 第3種才是精隨所在，可以分成3個步驟:
1. 先以node.Right為起點往他的left subtree向下尋找，目的是為了找到大於該node的最小值 minRight
2. 因為該node要被刪除，所以將她原本的node.Left subtree接到剛剛找到 minRight 上
3. 最後一步就是直接回傳node.Right，意味著直接跳過了該node用node.Right取代它的位置也就等同於刪除他，在前面一個步驟也幫node.Left找到合理的位置，大功告成!

### Recursive解法

• time complexity: O(log(n)) , space complexity: O(1)

Runtime: 12 ms, faster than 82.28% of Go online submissions for Delete Node in a BST.

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 `````` ``````/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func deleteNode(root *TreeNode, key int) *TreeNode { if root == nil { return nil } if root.Val > key { root.Left = deleteNode(root.Left, key) }else if root.Val < key { root.Right = deleteNode(root.Right, key) }else { if root.Right == nil { return root.Left }else if root.Left == nil { return root.Right } minRight := root.Right for minRight.Left != nil { minRight = minRight.Left } minRight.Left = root.Left return root.Right } return root } ``````