栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

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

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

【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:传送门

文章小尾巴

文章写作、模板、文章小尾巴可参考:《写作“小心思”》

  感谢你看到最后,最后再说两点~
  ①如果你持有不同的看法,欢迎你在文章下方进行留言、评论。
  ②如果对你有帮助,或者你认可的话,欢迎给个小点赞,支持一下~
  我是南方者,一个热爱计算机更热爱祖国的南方人。

  (文章内容仅供学习参考,如有侵权,非常抱歉,请立即联系作者删除。)

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/948933.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号