题目地址(450. 删除二叉搜索树中的节点)

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

题目描述

  1. 给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
  3. 一般来说，删除节点可分为两个步骤：
  5. 首先找到需要删除的节点；
  6. 如果找到了，删除它。
  10. 示例 1:
  12. 输入：root = [5,3,6,2,4,null,7], key = 3
  13. 输出：[5,4,6,2,null,null,7]
  14. 解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
  15. 一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
  16. 另一个正确答案是 [5,2,6,null,4,null,7]。
  21. 示例 2:
  23. 输入: root = [5,3,6,2,4,null,7], key = 0
  24. 输出: [5,3,6,2,4,null,7]
  25. 解释: 二叉树不包含值为 0 的节点
  28. 示例 3:
  30. 输入: root = [], key = 0
  31. 输出: []
  35. 提示:
  37. 节点数的范围 [0, 104].
  38. -105 <= Node.val <= 105
  39. 节点值唯一
  40. root 是合法的二叉搜索树
  41. -105 <= key <= 105
  45. 进阶： 要求算法时间复杂度为 O(h)，h 为树的高度。

前置知识


公司

  • 暂无

思路

这个问题稍微复杂，跟插入操作类似，先「找」再「改」
找到目标节点了，比方说是节点 A，如何删除这个节点，这是难点。因为删除节点的同时不能破坏 BST 的性质。有三种情况，用图片来说明。
情况 1：A 恰好是末端节点，两个子节点都为空，那么它可以当场删除。
image.png
情况 2：A 只有一个非空子节点，那么它要让这个孩子接替自己的位置。
image.png
情况 3：A 有两个子节点，麻烦了，为了不破坏 BST 的性质，A 必须找到左子树中最大的那个节点，或者右子树中最小的那个节点来接替自己。我们以第二种方式讲解。
image.png
注意一下，上述代码在处理情况 3 时通过一系列略微复杂的链表操作交换 root 和 minNode 两个节点：
有的读者可能会疑惑，替换 root 节点为什么这么麻烦，直接改 val 字段不就行了？看起来还更简洁易懂
仅对于这道算法题来说是可以的，但这样操作并不完美，我们一般不会通过修改节点内部的值来交换节点。
因为在实际应用中，BST 节点内部的数据域是用户自定义的，可以非常复杂，而 BST 作为数据结构（一个工具人），其操作应该和内部存储的数据域解耦，所以我们更倾向于使用指针操作来交换节点，根本没必要关心内部数据。
不过这里我们暂时忽略这个细节，旨在突出 BST 基本操作的共性，以及借助框架逐层细化问题的思维方式。

关键点


代码

  • 语言支持：Java

Java Code:

  2. /**
  3.  * Definition for a binary tree node.
  4.  * public class TreeNode {
  5.  *     int val;
  6.  *     TreeNode left;
  7.  *     TreeNode right;
  8.  *     TreeNode() {}
  9.  *     TreeNode(int val) { this.val = val; }
  10.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  11.  *         this.val = val;
  12.  *         this.left = left;
  13.  *         this.right = right;
  14.  *     }
  15.  * }
  16.  */
  17. class Solution {
  18.         public TreeNode deleteNode(TreeNode root, int key) {
  19.             if (root == null) {
  20.                 return null;
  21.             }
  22.             //首先在删除之前需要找到该元素
  23.             //如果找到该值 就开始删除逻辑
  24.             if (root.val == key) {
  25.                 //情况1 当两边都为空的时候 返回空值 这样就可以达到删除节点的目的 ->
  26.                 //<-而这种情况背下面的情况2覆盖了 当左或右为空 返回另一边的时候 返回的也是空值
  27.                 //情况2 当root的左边或者右边其中一个为空的时候 返回另一边 直接就将删除值覆盖了
  28.                 if (root.left == null) {
  29.                     return root.right;
  30.                 }
  31.                 if (root.right == null) {
  32.                     return root.left;
  33.                 }
  34.                 //情况3 两边都不为空 这时需要找到左子树最大值或右子树最小值 然后替换当前值
  35.                 //找到右子树最小值
  36.                 TreeNode min = getMin(root.right);
  37.                 //找到后还需要删掉右子树的最小值
  38.                 root.right = deleteNode(root.right, min.val);
  39.                 min.left = root.left;
  40.                 min.right = root.right;
  41.                 root = min;
  42.             } else if (key < root.val) {
  43.                 //如果root大于删除值 就在root左边找 反之在右边找 将找到的值返回给root
  44.                 root.left = deleteNode(root.left, key);
  45.             } else if (key > root.val) {
  46.                 root.right = deleteNode(root.right, key);
  47.             }
  48.             return root;
  49.         }
  50.         public TreeNode getMin(TreeNode root){
  51.             while (root.left != null) {
  52.                 root = root.left;
  53.             }
  54.             return root;
  55.         }
  56.     }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：450. 删除二叉搜索树中的节点 - 图4#card=math&code=O%28n%29&id=nawGX)
  • 空间复杂度：450. 删除二叉搜索树中的节点 - 图5#card=math&code=O%28n%29&id=ScJSd)