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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/delete-node-in-a-bst

题目描述

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

进阶：要求算法时间复杂度为 O(h)，h 为树的高度。

解题思路

本题总的来说分为两步，第一步是找到要删除的节点，
这个之前有一篇文章说过：二叉搜索树中的搜索
再就是找到后删除节点后，如何调整树的结构，使其还满足二叉搜索树的特性。

这里删除时，就要考虑三种情况了：
1.当前节点没有左右子节点，那就直接删除，
2.左右节点只有一个时，那就直接返回另外一个就行了。
3.第三种左右节点都有时。
我们要把右树上的最小节点替换过来，使其依然满足搜索二叉树的性质。

代码演示

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode deleteNode(TreeNode root, int key) {if(root == null){return null;}return process(root,key);}/*** 递归删除一个节点* @param root* @param val*/public static TreeNode process(TreeNode root,int val){if (root == null){return null;}if(root.val == val){//没有子节点，直接返回null 干掉当前节点if(root.left == null && root.right == null){return null;}// 左为null 时  返回右节点if (root.left == null){return root.right;}// 右为null 时  返回左节点if (root.right == null){return root.left;}//左右节点都有时//获取右子树上最小的节点TreeNode min = getMin(root.right);//删除右子树上最小的节点root.right =  process(root.right,min.val);//最小节点替换掉要删除的头节点min.left = root.left;min.right = root.right;root = min;//本题中也可以直接值替换// root.val = min.val;} else if (root.val > val) {root.left = process(root.left,val);} else if (root.val < val) {root.right = process(root.right,val);}return root;}/*** 获得最小节点，其实就是右树的最左节点*/public static TreeNode getMin(TreeNode root){while (root.left != null){root = root.left;}return root;}
}