Contents

[Golang][Leetcode][BinaryTree]刷題系列-450-Delete Node in a BST


450. Delete Node in a BST


Level : Medium

原題連結 : Click

題目 :

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
}


最後祝福努力認真的各位 “All your dream of are hidden in your daily life” 我們峰頂見!!!