一、题目粗心

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

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

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

示例 1:

输出：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]。

示例 2:

输出: root = [5,3,6,2,4,null,7], key = 0

输入: [5,3,6,2,4,null,7]

解释: 二叉树不蕴含值为 0 的节点

示例 3:

输出: root = [], key = 0

输入: []

提醒:

  • 节点数的范畴 [0, 104].
  • -105 <= Node.val <= 105
  • 节点值惟一
  • root 是非法的二叉搜寻树
  • -105 <= key <= 105

起源：力扣（LeetCode）
链接：https://leetcode.cn/problems/...
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

二、解题思路

这道题让咱们删除二叉搜寻树中的一个节点，难点在于删除完节点并补上那个节点的地位后还应该是一棵二叉搜寻树。被删除掉的节点地位，不肯定是由其左右节点补上，

         7        / \       4   8     /   \       2     6     \   /      3 5

下面这棵树，如果要删除节点4，那么应该将节点5补到4的地位，这样能力保障还是BST，后果是上面这棵树

         7        / \       5   8     /   \       2     6     \         3

递归思路：首先判断根节点是否为空，因为BST的性质：左 < 根 < 右，使得能够疾速定位到要删除的节点，对于以后节点值不等于key的状况，依据大小关系对其左右子节点别离调用递归函数。若以后节点就是要删除的节点，先判断若有一个子节点不存在，就将root指向另一个节点，如果左右节点都不存在，那么root就赋值为空了，也正确。难点就在于解决左右子节点都存在的状况，须要在右子树找到最濉址，即右子树中最左下方的节点，而后将该最小值赋值给root，而后再在右子树中调用递归函数来mbmw这个最小的节点。

三、解题办法

3.1 Java实现

public class Solution {    public TreeNode deleteNode(TreeNode root, int key) {        if (root == null) {            return null;        }        if (root.val > key) {            root.left = deleteNode(root.left, key);        } else if (root.val < key) {            root.right = deleteNode(root.right, key);        } else {            if (root.left == null || root.right == null) {                root = (root.left != null) ? root.left : root.right;            } else {                TreeNode cur = root.right;                while (cur.left != null) {                    cur = cur.left;                }                root.val = cur.val;                root.right = deleteNode(root.right, cur.val);            }        }        return root;    }}

四、总结小记

  • 2022/10/21 脑力劳动的人更容易摸鱼