Leetcode - Delete Node in a BST

https://leetcode.com/problems/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.

Note: Time complexity should be O(height of tree).

Example:

root = [5,3,6,2,4,null,7]
key = 3

    5
   / \
  3   6
 / \   \
2   4   7

1. If node doesn't have any kid, delete the node directly

2. If node has only kid, replace node with the kid

3. If node has two kids, find successor of node, replace node value with successor. Call DeleteNode recursively to delete successor.

4. To find sucessor, move to right, and then loop in left branch to get last one.

/**
 * 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
    }
    node := root
    var preNode *TreeNode
    for node != nil {
        if node.Val == key {
            break
        }
        preNode = node
        if node.Val > key {
            node = node.Left
        } else {
            node = node.Right
        }
    }
    if node == nil {
        return root
    }
    
    if node.Left == nil && node.Right == nil {
        if node == root {
            return nil
        }
        if preNode.Left == node {
            preNode.Left = nil
        } else {
            preNode.Right = nil
        }
        return root
    }
    if node.Left != nil && node.Right == nil {
        if node == root {
            return node.Left
        }
        if preNode.Left == node {
            preNode.Left = node.Left
        } else {
            preNode.Right = node.Left
        }
        return root
    }
    if node.Left == nil && node.Right != nil {
        if node == root {
            return node.Right
        }
        if preNode.Left == node {
            preNode.Left = node.Right
        } else {
            preNode.Right = node.Right
        }
        return root
    }
    if node.Left != nil && node.Right != nil {
        successor := getSuccessor(node)
        tmp := successor.Val        
        deleteNode(node, successor.Val)
        node.Val = tmp
    }
    return root
}

func getSuccessor(node *TreeNode) *TreeNode {
    node = node.Right
    for node.Left != nil {
        node = node.Left
    }
    return node
}

• 相关文章
• 全局相关文章