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

题目描述

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

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

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

示例 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, 10⁴].
-10⁵ <= Node.val <= 10⁵
节点值唯一
root 是合法的二叉搜索树
-10⁵ <= key <= 10⁵

进阶： 要求算法时间复杂度为 O (h)，h 为树的高度。

解法一：递归

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


/**
 * 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
    }
    if root.Val == key {
        if root.Right == nil {
            return root.Left
        } else {
            newRoot := root.Right
            parent := root
            for newRoot.Left != nil {
                parent = newRoot
                newRoot = newRoot.Left
            }
            newRoot.Left = root.Left
            if newRoot != root.Right {
                // 注意不要忘记执行 parent.Left = newRoot.Right
                parent.Left = newRoot.Right
                newRoot.Right = root.Right
            }
            return newRoot
        }
    } else if root.Val > key {
        root.Left = deleteNode(root.Left, key)
    } else {
        root.Right = deleteNode(root.Right, key)
    }
    return root
}

官方题解如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


func deleteNode(root *TreeNode, key int) *TreeNode {
    switch {
    case root == nil:
        return nil
    case root.Val > key:
        root.Left = deleteNode(root.Left, key)
    case root.Val < key:
        root.Right = deleteNode(root.Right, key)
    case root.Left == nil || root.Right == nil:
        if root.Left != nil {
            return root.Left
        }
        return root.Right
    default:
        successor := root.Right
        for successor.Left != nil {
            successor = successor.Left
        }
        successor.Right = deleteNode(root.Right, successor.Val)
        successor.Left = root.Left
        return successor
    }
    return root
}