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

leecode原题

题目

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

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

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

示例

示例 1:

输入：root = [5,3,6,2,4,null,7], key = 3
输出：[5,4,6,2,null,null,7]
解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
另一个正确答案是 [5,2,6,null,4,null,7]。

示例 2:

输入: root = [5,3,6,2,4,null,7], key = 0
输出: [5,3,6,2,4,null,7]
解释: 二叉树不包含值为 0 的节点

示例 3:

输入: root = [], key = 0
输出: []

提示：

• 节点数的范围 [0, 104].
• -105 <= Node.val <= 105
• 节点值唯一
• root 是合法的二叉搜索树
• -105 <= key <= 105

解题思路

思路

这里就把二叉搜索树中删除节点遇到的情况都搞清楚。

有以下五种情况：

1. 第一种情况：没找到删除的节点，遍历到空节点直接返回了

找到删除的节点

1. 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
2. 第三种情况：删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点
3. 第四种情况：删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
4. 第五种情况：左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。

总体来说，第5种情况，相对会复杂些。

实现

源码

func deleteNode(root *TreeNode, key int) *TreeNode {
    // 没找到
    if root == nil {
        return root
    }
    // 找到目标值
    if root.Val == key {
        // 节点的左右子树均为空，即该节点为叶子节点，舍弃即可
        if root.Left == nil && root.Right == nil {
            return nil
        }
        // 左子树为空，右子树非空, 右子树替换该节点
        if root.Left == nil && root.Right != nil {
            return root.Right
        }
        // 左子树非空，右子树为空，左子树替换该节点
        if root.Left != nil && root.Right == nil {
            return root.Left
        }
        // 左右子树均非空
        if root.Left != nil && root.Right != nil {
            // 找到右子树的最左叶子节点, 将左子树作为最左叶子节点的左子树插入
            tmp := root.Right
            for tmp.Left != nil {
                tmp = tmp.Left
            }
            tmp.Left = root.Left
            // 原节点左子树置空
            root.Left = nil
            // 原节点用右子树替换
            root = root.Right
            return root
        }
    }
    // 寻找左子树
    if key < root.Val {
        root.Left = deleteNode(root.Left, key)
    } else {
        root.Right = deleteNode(root.Right, key)
    }
    return root
}