LeetCode 450. 删除二叉搜索树中的节点 递归题解，熟用递归、理解BST结构。

题目

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

https://leetcode.cn/problems/delete-node-in-a-bst/

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

递归

树形问题非常适合用分治、递归的思路来做。

思路

先找val位置：

  1. 左子树上，递归到左子树；
  2. 右子树上，递归到右子树；
  3. 找到了待删节点：
    • 判断是否只有一个子节点，如果是，直接用另一边的子树节点顶上；
    • 如果不是，找到右子树最小节点，替换到当前节点位置，并删除；
    • 1962年，Hubbard 提出，Hubbard Deletion算法

复杂度分析

时间

递归遍历一个树的高度，时间复杂度O(n)。

空间

额外空间开销主要为递归调用栈，空间复杂度O(n)。

代码

 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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

/*
    * 执行用时：
    * 0 ms
    * , 在所有 Java 提交中击败了
    * 100.00%
    * 的用户
    * 内存消耗：
    * 42 MB
    * , 在所有 Java 提交中击败了
    * 8.44%
    * 的用户
    * 通过测试用例：
    * 91 / 91
    */

/**
    * 判断val位置：
    * 1. 左子树上，递归到左子树；
    * 2. 右子树上，递归到右子树；
    * 3. 找到了待删节点：
    * - 判断是否只有一个子节点，如果是，直接用另一边的子树节点顶上；
    * - 如果不是，找到右子树最小节点，替换到当前节点位置，并删除；
    * - 1962年，Hibbard 提出，Hibbard Deletion算法
    *
    * @param root 当前树根
    * @param val  待删除节点
    * @return 删除之后的整树根
    */
public TreeNode deleteNodeRecursion(TreeNode root, int val) {
    if (root == null) {
        return null;
    }
    if (root.val > val) {
        root.left = deleteNodeRecursion(root.left, val);
        return root;
    } else if (root.val < val) {
        root.right = deleteNodeRecursion(root.right, val);
        return root;
    } else {
        // val==node.val
        if (root.left == null) {
            return root.right;
        }
        if (root.right == null) {
            return root.left;
        }
        // 左右子节点均存在，将右子树中最小节点删除，同时将右子树最小节点替换到当前node位置
        TreeNode miniNode = findMiniNode(root.right);
        miniNode.right = removeMini(root.right);
        miniNode.left = root.left;
        return miniNode;
    }
}

// 返回当前node树上的最小节点
public TreeNode findMiniNode(TreeNode node) {
    if (node == null) {
        return null;
    }
    if (node.left == null) {
        return node;
    }
    return findMiniNode(node.left);
}

// 返回删除当前树最小节点后的根
public TreeNode removeMini(TreeNode node) {
    if (node == null) {
        return null;
    }
    if (node.left == null) {
        return node.right;
    }
    node.left = removeMini(node.left);
    return node;
}

迭代

迭代的方案可以将递归中额外的递归调用栈空间开销优化掉。

TBD

Ref