少女祈祷中...

题目

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

《代码随想录》算法视频公开课

力扣题目链接

示例1

  • 输入:root = [5,3,6,2,4,null,7], key = 3
  • 输出:[5,4,6,2,null,null,7]
  • 解释:给定需要删除的节点值是 3,所以我们首先找到 3 这个节点,然后删除它
    图示
    删除二叉搜索树中的节点
    示例2
  • 输入: root = [5,3,6,2,4,null,7], key = 0
  • 输出: [5,3,6,2,4,null,7]
  • 解释: 二叉树不包含值为 0 的节点
    示例3
  • 输入: root = [], key = 0
  • 输出: []

思路

删除结点可能出现的五种情况

  1. 没有找到key对应结点:
    • 没找到删除的节点,遍历到空节点直接返回了
  2. 找到key对应的结点:
    • key对应结点的左孩子为null,右孩子不为null,则直接返回右孩子
    • key对应结点的右孩子为null,左孩子不为null,则直接返回左孩子
    • 删除结点的右孩子为null,左孩子不为null,删除结点,左孩子补位,返回左孩子为根结点
    • 删除结点的左右孩子结点都不为空,则将删除结点的左子树头结点(左孩子)放到删除节点的右子树的最左面节点的左孩子上,返回删除节点右孩子为新的根节点。

注意:因为该题所提供的二叉树为搜索二叉树,即删除结点的左子树值皆小于右子树的值,即可将待删结点的左子树置于待删结点的右子树的左叶子结点下。

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

代码实现

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
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return root;
//当遍历到的结点值为待删结点时
if (root.val == key) {
if (root.left == null) {//待删结点的左结点为空,则返回右结点
return root.right;
} else if (root.right == null) {//待删结点的右结点为空,则返回左结点
return root.left;
} else {
//存储待删结点的右子树头结点
TreeNode cur = root.right;
while (cur.left != null) {//找到待删结点的左叶子结点,作为待删结点左子树的挂载点
cur = cur.left;
}
cur.left = root.left;//挂载待删结点的左子树到待删结点的右子树的左叶子结点下
root = root.right;//删除待删结点
return root;
}
}
if (root.val > key) root.left = deleteNode(root.left, key);//当key小于当前结点值时向左树寻找
if (root.val < key) root.right = deleteNode(root.right, key);//当key大于当前结点时向右树寻找
return root;//仍然为传入的root
}
}