450.删除二叉搜索树中的节点

leetcode

递归方法

1. 根据二叉搜索树的特性寻找要删除的节点
2. 如果删除节点就是叶子节点，直接删除
3. 如果删除节点的左孩子或者有孩子为空，则直接删除当前节点，把非空的孩子节点替换当前节点
4. 如果删除节点左右孩子都不为空，则寻找大于删除节点的最小节点来替代删除节点，这个节点在删除节点右子树的最左端叶子节点。该节点没有左子树，删除该节点后也比较好处理，且可以保证被删除节点的左子树都小于它，被删除节点的右子树也都大于它。
5. 特殊情况，若删除节点右子树的最左端叶子节点就是删除节点的右孩子，则只需替换右子树的最左端叶子节点的左孩子为删除节点的左孩子即可。

时间复杂度：O(N)
空间复杂度：O(N)

func deleteNode(root *TreeNode, key int) *TreeNode {
    if root == nil {
        return nil
    }

    if root.Val < key {
        root.Right = deleteNode(root.Right, key)
    } else if root.Val > key {
        root.Left = deleteNode(root.Left, key)
    } else {
        if root.Left == nil || root.Right == nil {
            if root.Left == nil {
                return root.Right
            } else {
                return root.Left
            }
        } else {
            tempParent := root
            temp := root.Right

            // root.Right 就是右子树的最小值
            if temp.Left == nil {
                temp.Left = root.Left
                return temp
            }

            // 寻找右子树的最小值
            for temp.Left != nil {
                tempParent = temp
                temp = temp.Left
            }

            temp.Left = root.Left
            tempParent.Left = temp.Right
            temp.Right = root.Right
            return temp
        }
    }

    return root
}