DAY 26
0
Software Development

## Day.26 Binary Search Tree IV

1. 左右的child都為空

1. 左邊的child有值，但右節點為空

1. 右邊child有值，但它底下沒有左child

1. 右邊child有值，底下有左child

4個case都講完了，就可以轉化為程式

Leetcode #450. Delete Node in a BST

``````func deleteNode(root *TreeNode, key int) *TreeNode {
var preNode *TreeNode
currentNode := root

// 先找到要刪的節點
for {
// 找不到
if currentNode == nil {
return root
}

if currentNode.Val == key {
break
}

if key < currentNode.Val {
// 往左找
preNode = currentNode
currentNode = currentNode.Left
} else {
// 往右找
preNode = currentNode
currentNode = currentNode.Right
}
}

// case.1 左右chil為空
if currentNode.Left == nil && currentNode.Right == nil {
// 刪的是root節點
if preNode == nil {
root = nil
return root
}

if currentNode.Val < preNode.Val {
preNode.Left = nil
} else {
preNode.Right = nil
}

return root
}

// case.2 左child有東西 右child為空
if currentNode.Left != nil && currentNode.Right == nil {
// 刪的是root節點
if preNode == nil {
root = currentNode.Left
return root
}

// 判斷要接到上一個節點的左邊還是加邊
if currentNode.Val < preNode.Val {
preNode.Left = currentNode.Left
} else {
preNode.Right = currentNode.Left
}

return root
}

// case.3 右child有東西 但它沒有左child
if currentNode.Right != nil && currentNode.Right.Left == nil {
// 把目前節點的左child 接到右child的左child
currentNode.Right.Left = currentNode.Left

// 刪的是root節點
if preNode == nil {
root = currentNode.Right
return root
}

// 判斷要接到上一個節點的左邊還是加邊
if currentNode.Val < preNode.Val {
preNode.Left = currentNode.Right
} else {
preNode.Right = currentNode.Right
}

return root
}

// case.4 右child擁有左child
// 從左child開始找 找到最小的值
leftMostParent := currentNode.Right
leftMost := currentNode.Right.Left
for leftMost.Left != nil {
leftMostParent = leftMost
leftMost = leftMost.Left
}

leftMostParent.Left = leftMost.Right
leftMost.Left = currentNode.Left
leftMost.Right = currentNode.Right

// 刪的是root節點
if preNode == nil {
root = leftMost
return root
}

if leftMost.Val < preNode.Val {
preNode.Left = leftMost
} else {
preNode.Right = leftMost
}

return root
}
``````
``````Runtime: 12 ms, faster than 86.46% of Go online submissions for Delete Node in a BST.
Memory Usage: 7.1 MB, less than 96.88% of Go online submissions for Delete Node in a BST.
``````