【JAVA】【刷题子】450. 删除二叉搜索树中的节点

一、题目与题目分析

题目

　　给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。　　一般来说，删除节点可分为两个步骤：

• 首先找到需要删除的节点；
• 如果找到了，删除它。 （题目来源：力扣：450. 删除二叉搜索树中的节点）

题目分析

做题前，首先要明白什么是二叉搜索树。二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）。　　设x是二叉搜索树中的一个结点。如果y是x左子树中的一个结点，那么y.key≤x.key。如果y是x右子树中的一个结点，那么y.key≥x.key。 　　同时，还有以下三个特征：

• 1.若任意结点的左子树不空，则左子树上所有结点的值均不大于它的根结点的值。
• 2.若任意结点的右子树不空，则右子树上所有结点的值均不小于它的根结点的值。
• 3.任意结点的左、右子树也分别为二叉搜索树。 　　对于二叉搜索树已经有所了解了，我们就是要从二叉搜索树里找需要删除的节点，进行替换。即把当前需要删除的节点，左孩（树）最右叶进行替换；或右孩（树）最左叶进行替换。

二、整体逻辑与主要代码

题目分析已经比较清楚了，接下来我们进入代码设计。

整体逻辑

• 1. 找到需要删除的节点
• 1. 替换，把该节点对应下的左孩最大值或右孩最小值替换目前节点的位置。

主要代码

整体逻辑清晰了之后，同时也有较清楚的注释。直接来看代码吧！ （如有不懂的或者更好的建议，欢迎评论区分享友友的看法哈~）

	public static TreeNode deleteNode(TreeNode root, int key) {
		if (root == null) {
			return null;
		}
		if (root.val > key) {
			// 删除节点在左边的子树里
			root.left = deleteNode(root.left, key);
			return root;
		}
		if (root.val < key) {
			// 删除节点在右边的子树里
			root.right = deleteNode(root.right, key);
			return root;
		}
		// 当前的节点是删除节点（即key == root.val）
		if (null == root.left) { // 左边没有节点，返回右子节点为新节点
			return root.right;
		}
		if (null == root.right) { // 右子没有节点，返回左子节点为新节点
			return root.left;
		}
		// 左右子节点都存在，选择后继节点的（右子最左的子叶）作为新的节点。（左子最右即左子里最大的子叶节点也可）
		TreeNode next = rightMin(root.right); // 找右子里最小（左）的节点
		next.right = replaceRightMin(root.right); // 替换该节点
		next.left = root.left; // 当前的左边不变
		return next;
	}

	public static TreeNode rightMin(TreeNode node) {
		if (node.left == null) { // 找最左边的节点
			return node;
		}
		return rightMin(node.left);
	}

	public static TreeNode replaceRightMin(TreeNode node) {
		if (node.left == null) { // 左子为空，返回右子
			return node.right;
		}
		node.left = replaceRightMin(node.left); // 左子不为空，继续左子
		return node;
	}

三、结果展示

四、总结

基于他人的注解，这何尝也不是一种学习呢？（本期想法和逻辑是参考于这个力扣Angus-Liu解答评论的）

题目数据库

Gitee：传送门

文章小尾巴

文章写作、模板、文章小尾巴可参考：《写作“小心思”》 　　感谢你看到最后，最后再说两点~　　①如果你持有不同的看法，欢迎你在文章下方进行留言、评论。　　②如果对你有帮助，或者你认可的话，欢迎给个小点赞，支持一下~　　我是南方者，一个热爱计算机更热爱祖国的南方人。　　（文章内容仅供学习参考，如有侵权，非常抱歉，请立即联系作者删除。）