乐趣区

关于leetcode:leetcode-450-Delete-Node-in-a-BST-删除二叉搜索树中的节点-中等

jiezi

一、题目粗心

给定一个二叉搜寻树的根节点 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 脑力劳动的人更容易摸鱼
退出移动版