二叉树

题目

给定一个二叉搜索树的根节点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
  }
}