二叉树：删除节点

/*
递归解法：
1.找到需要删除的节点
2.删除的节点只有右子树或者左子树，直接将右子树或者左子树的根节点当作这个删除的节点
3.删除的节点左右子树都存在的情况下，左子树的最大节点也叫做前驱当作删除节点，
或者将右子树的最小节点也就称作后驱当作删除节点。
*/

/*
递归解法：
1.找到需要删除的节点
2.删除的节点只有右子树或者左子树，直接将右子树或者左子树的根节点当作这个删除的节点
3.删除的节点左右子树都存在的情况下，左子树的最大节点也叫做前驱当作删除节点，
或者将右子树的最小节点也就称作后驱当作删除节点。
*/

func deleteNode(root *TreeNode, key int) *TreeNode {
    if root == nil {
        return nil
    }
    if key < root.Val {
        root.Left = deleteNode(root.Left,key)
        return root
    }
    if key > root.Val {
        root.Right = deleteNode(root.Right,key)
        return root
    }
    // 这里通过递归已经找到了要删除的节点,此时因为递归的原因还是root这个指针
    if root.Right == nil {
        return root.Left
    }
    if root.Left == nil {
        return root.Right
    }
    // 后驱的方法来替换当前节点
    min := root.Right
    for min.Left != nil {
        min = min.Left
    }
    root.Val = min.Val // 替换需要删除的节点的数值，这里就是复制
    root.Right = deleteMin(root.Right) // 这里把右子树中移动过来的那个最小节点删除掉
    return root
}
func deleteMin(root *TreeNode) *TreeNode{
    // 左子树不在的话，表示这个节点就是要删除的最小节点
    // 存在两种情况，一：这个节点就是叶子节点，直接通过赋值为nil, 来当作删除节点。
    // 二：这个节点没有左子树，只有右子树，这样的话，需要将右子树替换成该节点
    if root.Left == nil { 
        right := root.Right
        root.Right = nil 
        return right
    }
    root.Left = deleteMin(root.Left) // 左子树一直在的话，就一直通过左子树去找最小节点
    return root
}

func deleteNode(root *TreeNode, key int) *TreeNode {
    if root == nil {
        return nil
    }
    if key < root.Val {
        root.Left = deleteNode(root.Left,key)
        return root
    }
    if key > root.Val {
        root.Right = deleteNode(root.Right,key)
        return root
    }
    // 这里通过递归已经找到了要删除的节点,此时因为递归的原因还是root这个指针
    if root.Right == nil {
        return root.Left
    }
    if root.Left == nil {
        return root.Right
    }
    // 前驱的方法来替换当前节点
    max := root.Left
    for max.Right != nil {
        max = max.Right
    }
    root.Val = max.Val
    root.Left = deleteMax(root.Left)
    return root
}

func deleteMax(root *TreeNode) *TreeNode {
    if root.Right == nil {
        left := root.Left
        root.Left = nil 
        return left
    }
    root.Right = deleteMax(root.Right)
    return root
}
/*
递归解法：
1.找到需要删除的节点
2.删除的节点只有右子树或者左子树，直接将右子树或者左子树的根节点当作这个删除的节点
3.删除的节点左右子树都存在的情况下，左子树的最大节点也叫做前驱当作删除节点，
或者将右子树的最小节点也就称作后驱当作删除节点。
*/