二叉搜索树中的删除

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

1. 首先找到需要删除的节点；
2. 如果找到了，删除它。

func deleteNode(root *TreeNode, key int) *TreeNode {
    if root == nil {
        return nil
    } else if key < root.Val {
        root.Left = deleteNode(root.Left, key)
    } else if key > root.Val {
        root.Right = deleteNode(root.Right, key)
    } else {
        if root.Left == nil && root.Right == nil { // 叶子节点 则删掉
            root = nil
        } else if root.Right != nil {
            // 非叶子节点且有右节点 该节点可以由后继节点替代 并递归删除后继节点
            root.Val = successor(root).Val
            root.Right = deleteNode(root.Right, root.Val)
        } else {
            // 非叶子节点且有左节点 该节点可以由前驱节点替代 并递归删除前驱节点
            root.Val = predecessor(root).Val
            root.Left = deleteNode(root.Left, root.Val)
        }
    }
    return root
}

// 后继节点 先取当前节点的右节点 然后一直取它的左节点 直到空
func successor(root *TreeNode) *TreeNode {
    p := root.Right
    for p.Left != nil {
        p = p.Left
    }
    return p
}

// 前驱节点 取当前节点的左节点 然后一直取它的右节点直到空
func predecessor(root *TreeNode) *TreeNode {
    p := root.Left
    for root.Right != nil {
        p = p.Right
    }
    return p
}

看注释即可，将删除的情形分为三种。