day18|235. 二叉搜索树的最近公共祖先、701.二叉搜索树中的插入操作、450.删除二叉搜索树中的节点

news/2023/6/7 1:18:33

235. 二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

例如,给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8

输出: 6

解释: 节点 2 和节点 8 的最近公共祖先是 6。  

示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4

输出: 2

解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。  

问题分析:

 利用二叉搜索树的特性,有序。当p和q的值小于根节点,说明都在左子树,当p、q的值大于根节点,说明都在右子树,如果根节点的值在p、q的之间,说明此时根节点就是最近的公共祖先。此题不分前中后序,中在哪里都无所谓。

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root==null) return null;if (root.val>p.val&&root.val>q.val){TreeNode left=lowestCommonAncestor(root.left,p,q);if (root!=null) return left;}if (root.val<p.val&&root.val<q.val){TreeNode right=lowestCommonAncestor(root.right,p,q);if (root!=null) return right;}return root;}
}

 701.二叉搜索树中的插入操作

给定二叉搜索树(BST)的根节点 root 和要插入树中的值 value ,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ,新值和原始二叉搜索树中的任意节点值都不同。

注意,可能存在多种有效的插入方式,只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。

示例 1:

输入:root = [4,2,7,1,3], val = 5

输出:[4,2,7,1,3,5]

解释:另一个满足题目要求可以通过的树是: 

示例 2:

输入:root = [40,20,60,10,30,50,70], val = 25

输出:[40,20,60,10,30,50,70,null,null,25]  

示例 3:

输入:root = [4,2,7,1,3,null,null,null,null,null,null], val = 5

输出:[4,2,7,1,3,5] 

问题分析:

每一个节点都能找到自己的位置,当遍历到null的位置,即找到了插入的位置,定义新节点,并返回此节点,为了返回给上一层节点,定义上一层节点的左/右子树=node(下一层递归的函数所return的node),所以递归的函数有返回值,目的是返回下一层的节点。

class Solution {public TreeNode insertIntoBST(TreeNode root, int val) {if (root==null) {//已找到位置TreeNode node=new TreeNode(val);return node;//为了给上一层提供左/右子树}if (root.val>val){root.left=insertIntoBST(root.left,val);//下层return了node,被上层接住}if (root.val<val){root.right=insertIntoBST(root.right,val);}return root;//记得最后返回头节点}
}

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

给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。

一般来说,删除节点可分为两个步骤:

  1. 首先找到需要删除的节点;
  2. 如果找到了,删除它。

示例 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

输出: []

问题分析:

 终止条件:

  • 第一种情况:没找到删除的节点,遍历到空节点直接返回了
  • 找到删除的节点
    • 第二种情况:左右孩子都为空(叶子节点),直接删除节点, 返回null为根节点
    • 第三种情况:删除节点的左孩子为空,右孩子不为空,删除节点,右孩子补位,返回右孩子为根节点
    • 第四种情况:删除节点的右孩子为空,左孩子不为空,删除节点,左孩子补位,返回左孩子为根节点
    • 第五种情况:左右孩子节点都不为空,右继承,则将删除节点的左子树头结点(左孩子)放到删除节点的右子树的最左面节点的左孩子上,返回删除节点右孩子为新的根节点。

最后单层逻辑再用根节点的左右孩子接住返回值。最后返回根节点。

class Solution {public TreeNode deleteNode(TreeNode root, int key) {if (root==null) return null;if (root.val==key){//找到删除的节点if (root.left==null&&root.right==null) return null;//把结果返回上一层else if (root.left!=null&&root.right==null)  return root.left;//把左节点接到上一层的上一层else if (root.left==null&&root.right!=null) return root.right;else {//左右都不为空TreeNode cur=root.right;//右孩子继位成为根节点while(cur.left!=null){//右继位,找到原左子树放到右子树的左节点的最下面cur=cur.left;}cur.left=root.left;//把原左子树挪到新位置return root.right;//右继位}}//终止条件结束//单层逻辑开始if (root.val>key) root.left=deleteNode(root.left,key);//接住下一层return的节点if (root.val<key) root.right=deleteNode(root.right,key);return root;}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.exyb.cn/news/show-4566593.html

如若内容造成侵权/违法违规/事实不符,请联系郑州代理记账网进行投诉反馈,一经查实,立即删除!

相关文章

HDU 6083 度度熊的午饭时光(01背包+记录路径)

http://acm.hdu.edu.cn/showproblem.php?pid6083 题意&#xff1a; 思路&#xff1a; 01背包路径记录。 题目有点坑&#xff0c;我一开始逆序枚举菜品&#xff0c;然后一直WA&#xff0c;可能这样的话路径记录会有点问题。 1 #include<iostream>2 #include<algorithm…

冥王星P的编曲日志《时光的眼泪》

某一时刻突然意识到应该记录下作曲编曲的过程及亮点&#xff0c;以实现代码的重用&#xff08;bushi&#xff09; 让我们回到时代久远的第一个工程《时光的眼泪》 乐器配置情况流行抒情的基本配置&#xff0c;主要是仿照letter song。在第二段主歌加了电吉他扫弦&#xff08;仿…

【万人围观】20位著名作家,100句惊艳了时光的名句

转载自语文高手微信号&#xff08;ID&#xff1a;ywgaoshou&#xff09; 等时间的人&#xff0c;就是浪费时间的人。 01 鲁迅 1. 惟沉默是最高的轻蔑。 2. 勇者愤怒&#xff0c;抽刃向更强者&#xff1b;怯者愤怒&#xff0c;却抽刃向更弱者。 3. 我之所谓生存&#xff0c;并不…

52 文本预处理 动手学深度学习 PyTorch版 李沐视频课笔记

动手学深度学习 PyTorch版 李沐视频课笔记 李沐视频课笔记其他文章目录链接(不定时更新) 文章目录动手学深度学习 PyTorch版 李沐视频课笔记一、文本预处理1. 引包2. 将数据集读取到多行文本组成的列表中3. 每个文本序列又被拆分成一个标记列表4. 构建⼀个字典&#xff0c;通常…

软件测试52讲读书笔记

最近要做功能测试和性能测试&#xff0c;临时抱佛脚&#xff0c;学习点可用的概念和术语&#xff0c;有个大概的认知。 测试需求 一个质量过硬的软件系统&#xff0c;除了显式功能性需求以外&#xff0c;其他的非功能性需求即隐式功能性需求也是极其关键的。 显式功能性需求&a…

【有利可图网】PS教程:利用PS制作时光沙漏

先看效果图&#xff1a; 1.首先新建画布600*800px,然后画个矩形做底色&#xff0c;填充颜色如下&#xff1a; 2.然后我们来制作这个沙漏的顶部&#xff0c;使用椭圆工具画好圆&#xff0c;再来个渐变色参数如下: 3.然后用矩形工具和椭圆工具制作沙漏上部的底部形状&#xff0c;…

python学习--爬取时光网top100电影名,导演,评分

python学习--爬取时光网top100电影名&#xff0c;导演&#xff0c;评分一、思路二、代码三、写在最后一、思路 1.第一页的网址&#xff1a;http://www.mtime.com/top/movie/top100/&#xff0c; 第二页网址&#xff1a;http://www.mtime.com/top/movie/top100/index-2.html 两…

【Python3爬虫】破解时光网登录加密参数并实现模拟登录

一、站点分析 MTime 时光网是一个电影媒体与电商服务平台&#xff0c;而这次做的模拟登录则是依靠其手机端站点&#xff0c;站点地址为&#xff1a;https://m.mtime.cn/#。切换到登录页面&#xff0c;再分别输入账号和错误的密码&#xff0c;点击登录&#xff0c;登录失败&…