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

题目描述

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

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

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

输入输出

1
2
3
4
5
6
7
8
9
10
输入：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], 如下图所示。
                5
               / \
              2   6
               \   \
                4   7

大致思路

  1. 如果目标节点大于当前节点值，则去右子树中删除；
  2. 如果目标节点小于当前节点值，则去左子树中删除；
  3. 如果目标节点就是当前节点，分为以下三种情况：
    1. 其无左子：其右子顶替其位置，删除了该节点；
    2. 其无右子：其左子顶替其位置，删除了该节点；
    3. 其左右子节点都有：其左子树转移到其右子树的最左节点的左子树上，然后右子树顶替其位置，由此删除了该节点。
1
2
3
4
5
6
7
    4                                 6
   / \                               / \
  2   6        删除完->              5   7
 / \ / \                           /
1  3 5  7                         2
                                 / \
                                1   3

性能分析：

  1. 时间复杂度：$O(H)$，H是树的高度，寻找目标节点最坏情况需要$O(H)$，删除操作最坏情况也需要$O(H)$；
  2. 空间复杂度：$O(H)$，递归栈的深度最坏情况为树的高度；

java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root == null) return null;
        if(key > root.val){
            root.right = deleteNode(root.right, key);
        }
        else if(key < root.val){
            root.left = deleteNode(root.left, key);
        }
        else{
            if(root.right == null) return root.left;
            else if(root.left == null) return root.right;
            else if(root.left != null && root.right != null){
                TreeNode tmp = root.right;//6
                while(tmp.left != null){
                    tmp = tmp.left;//5
                }
                tmp.left = root.left;
                root = root.right;
            }
        }
        return root;
    }
}