代码随想录训练营Day22:● 235. 二叉搜索树的最近公共祖先 ● 701.二叉搜索树中的插入操作 ● 450.删除二叉搜索树中的节点

本文主要是介绍代码随想录训练营Day22:● 235. 二叉搜索树的最近公共祖先 ● 701.二叉搜索树中的插入操作 ● 450.删除二叉搜索树中的节点,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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

题目链接

https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/description/

题目描述

相较于前一天的题不同,昨天的题是二叉树,这次重点强调了是二叉搜索树
在这里插入图片描述

思路

1、迭代法

因为二叉搜索树本身就是有序的,所以不需要去管前中后序三种遍历方法,直接判断大小即可整体思路就是判断 p,q 节点的值与根节点的大小,如果同时小于根节点,那公共祖先就在根节点的左子树 如果同时大于根节点,那么公共祖先就在根节点的右子树, 如果根节点的值介于两个节点之间,说明根节点就是祖先

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

2、递归法

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){return lowestCommonAncestor(root.left,p,q);}if(root.val<p.val&&root.val<q.val){return lowestCommonAncestor(root.right,p,q);}return root;}
}

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

题目链接

https://leetcode.cn/problems/insert-into-a-binary-search-tree/description/

题目描述

在这里插入图片描述

思路

public TreeNode insertIntoBST(TreeNode root, int val) {//递归方法//如果当前节点为空,说明此位置就是新节点将要插入的位置if(root==null) return new TreeNode(val);//如果根节点的值大于目标值,则向根节点的左侧递归//再判断如果根节点的左孩子不为空,继续递归,为空,就插入这里if(root.val>val){if(root.left!=null){insertIntoBST(root.left,val);}else {root.left = new TreeNode(val);}}//根节点大于目标值的思路类似上边if(root.val<val){if(root.right!=null){insertIntoBST(root.right,val);}else {root.right = new TreeNode(val);}}return root;
}

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

题目链接

https://leetcode.cn/problems/delete-node-in-a-bst/description/

题目描述

在这里插入图片描述

思路

第五种情况的处理逻辑:
在这里插入图片描述

class Solution {public TreeNode deleteNode(TreeNode root, int key) {//本题可以分为五种情况//1、没有找到想要删除的元素//2、找到了想要删除的元素,且删除的元素是叶子节点,即左右孩子均为空//3、找到了想要删除的元素,且删除的元素左孩子不为空右孩子为空//4、找到了想要删除的元素,且删除的元素左孩子为空右孩子不为空//5、找到了想要删除的元素,且删除的元素左右孩子均不为空if(root==null) return root;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);}if(root.val<key){//返回的节点应该用当前节点的右孩子接住root.right = deleteNode(root.right,key);}return root;}
}

这篇关于代码随想录训练营Day22:● 235. 二叉搜索树的最近公共祖先 ● 701.二叉搜索树中的插入操作 ● 450.删除二叉搜索树中的节点的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/807042

相关文章

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画(下)

【课程链接】 AntV G6:深入图形与图形分组、自定义节点、节点动画(下)_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中,应该怎样去计算和绘制图形,如何给一个图形制作不间断的动画,以及在鼠标事件之后产生动画。(有点难,需要好好理解) <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

hdu1240、hdu1253(三维搜索题)

1、从后往前输入,(x,y,z); 2、从下往上输入,(y , z, x); 3、从左往右输入,(z,x,y); hdu1240代码如下: #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc

电脑桌面文件删除了怎么找回来?别急,快速恢复攻略在此

在日常使用电脑的过程中,我们经常会遇到这样的情况:一不小心,桌面上的某个重要文件被删除了。这时,大多数人可能会感到惊慌失措,不知所措。 其实,不必过于担心,因为有很多方法可以帮助我们找回被删除的桌面文件。下面,就让我们一起来了解一下这些恢复桌面文件的方法吧。 一、使用撤销操作 如果我们刚刚删除了桌面上的文件,并且还没有进行其他操作,那么可以尝试使用撤销操作来恢复文件。在键盘上同时按下“C

poj1330(LCA最近公共祖先)

题意:求最近公共祖先 思路:之前学习了树链剖分,然后我就用树链剖分的一小部分知识就可以解这个题目了,记录每个结点的fa和depth。然后查找时,每次将depth大的结点往上走直到x = y。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring>

活用c4d官方开发文档查询代码

当你问AI助手比如豆包,如何用python禁止掉xpresso标签时候,它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

day-51 合并零之间的节点

思路 直接遍历链表即可,遇到val=0跳过,val非零则加在一起,最后返回即可 解题过程 返回链表可以有头结点,方便插入,返回head.next Code /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}*

计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

🍊作者:计算机编程-吉哥 🍊简介:专业从事JavaWeb程序开发,微信小程序开发,定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事,生活就是快乐的。 🍊心愿:点赞 👍 收藏 ⭐评论 📝 🍅 文末获取源码联系 👇🏻 精彩专栏推荐订阅 👇🏻 不然下次找不到哟~Java毕业设计项目~热门选题推荐《1000套》 目录 1.技术选型 2.开发工具 3.功能

hdu 4517 floyd+记忆化搜索

题意: 有n(100)个景点,m(1000)条路,时间限制为t(300),起点s,终点e。 访问每个景点需要时间cost_i,每个景点的访问价值为value_i。 点与点之间行走需要花费的时间为g[ i ] [ j ] 。注意点间可能有多条边。 走到一个点时可以选择访问或者不访问,并且当前点的访问价值应该严格大于前一个访问的点。 现在求,从起点出发,到达终点,在时间限制内,能得到的最大