leetcode分类刷题:二叉树(八、二叉搜索树特有的自顶向下遍历)

news/2025/3/17 16:23:45/

二叉搜索树是一个有序树:每个二叉树都满足左子树上所有节点的值均小于它的根节点的值,右子树上所有节点的值均大于它的根节点的值;利用该性质,可以实现二叉搜索树特有的自顶向下遍历

700. 二叉搜索树中的搜索

思路1、自顶向下的遍历:利用二叉搜索树有序性的性质,直接迭代法求解
思路2、递归-重复逻辑:对每个二叉树根节点判断值是否相等、根据值大小关系搜索左右子树

'''
700. 二叉搜索树中的搜索
给定二叉搜索树(BST)的根节点root和一个整数值val。
你需要在 BST 中找到节点值等于val的节点。 返回以该节点为根的子树。 如果节点不存在,则返回null。
示例 1:输入:root = [4,2,7,1,3], val = 2输出:[2,1,3]
思路1、自顶向下的遍历:利用二叉搜索树有序性的性质,直接迭代法求解
思路2、递归-重复逻辑:对每个二叉树根节点判断值是否相等、根据值大小关系搜索左右子树
'''
class Solution:# 利用二叉搜索树有序性的性质,直接迭代法求解def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:while root != None:if root.val > val:root = root.leftelif root.val < val:root = root.rightelse:  # root.val == valreturn rootreturn None# 递归-重复逻辑:对每个二叉树根节点判断值是否相等、根据值大小关系搜索左右子树def searchBSTRecursive(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:# 简单情况if root == None:return Noneelif root.val == val:return root# 重复逻辑elif root.val > val:return self.searchBSTRecursive(root.left, val)elif root.val < val:return self.searchBSTRecursive(root.right, val)

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

思路:和 “700. 二叉搜索树中的搜索”是一样的题,后者是寻找一个数找到并返回以该数为根节点的子树,本题是寻找同时包含两个数的子树
从上到下的遍历:利用二叉搜索树有序性的性质,只要从上到下遍历的时候,cur节点是数值在[p, q]区间中则说明该节点cur就是最近公共祖先了
递归:重复操作:对每个二叉树根节点判断值是否在[p, q]区间、根据值大小关系搜索左右子树

'''
235. 二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
示例 1:输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8输出: 6 解释: 节点 2 和节点 8 的最近公共祖先是 6。
思路:和 “700. 二叉搜索树中的搜索”是一样的题,后者是寻找一个数找到并返回以该数为根节点的子树,本题是寻找同时包含两个数的子树
从上到下的遍历:利用二叉搜索树有序性的性质,只要从上到下遍历的时候,cur节点是数值在[p, q]区间中则说明该节点cur就是最近公共祖先了。
递归:重复操作:对每个二叉树根节点判断值是否在[p, q]区间、根据值大小关系搜索左右子树
'''
class Solution:def lowestCommonAncestor(self, root: Optional[TreeNode], p: Optional[TreeNode], q: Optional[TreeNode]) -> Optional[TreeNode]:while root != None:if root.val > p.val and root.val > q.val:root = root.leftelif root.val < p.val and root.val < q.val:root = root.rightelse:  # 包含了很多种情况(p、q哪个大或小),总体来说就是cur节点是数值在[p, q]区间中,是同时包含这两个数的子树return rootreturn None
文章来源:https://blog.csdn.net/qq_39975984/article/details/133948227
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:
http://www.ppmy.cn/news/1188928.html

相关文章

PyQt5:构建目标检测算法GUI界面 (附python代码)

文章目录 1.界面2.代码3.Analyze 1.界面 目标检测算法一般就是检测个图片&#xff0c;然后显示图片结果。 最简单的情况&#xff0c;我们需要一个按钮读取图片&#xff0c;然后后有一个地方显示图片。 2.代码 import sys import numpy as np from PIL import Imagefrom PyQt…

发布不到一月的4+经典单细胞+预后模型生信思路,可复现可升级

今天给同学们分享一篇单细胞预后模型的生信文章“Integrating single-cell and bulk RNA sequencing to predict prognosis and immunotherapy response in prostate cancer”&#xff0c;这篇文章于2023年9月20日发表在Scientific Reports期刊上&#xff0c;影响因子为4.6。 前…

Mybatis—XML配置文件、动态SQL

学习完Mybatis的基本操作之后&#xff0c;继续学习Mybatis—XML配置文件、动态SQL。 目录 Mybatis的XML配置文件XML配置文件规范XML配置文件实现MybatisX的使用 Mybatis动态SQL动态SQL-if条件查询 \<if\>与\<where\>更新员工 \<set\>小结 动态SQL-\<forea…

Ubuntu上安装配置Nginx

要在 Ubuntu 上安装 Nginx&#xff0c;请按照以下步骤进行操作&#xff1a; 打开终端&#xff1a;可以使用快捷键 Ctrl Alt T 打开终端&#xff0c;或者在开始菜单中搜索 “Terminal” 并点击打开。 更新软件包列表&#xff1a;在终端中运行以下命令&#xff0c;以确保软件包…

041-第三代软件开发-QCustcomPlot波形标注

第三代软件开发-QCustcomPlot波形标注 文章目录 第三代软件开发-QCustcomPlot波形标注项目介绍QCustcomPlot波形标注效果初始化绘制 关键字&#xff1a; Qt、 Qml、 关键字3、 关键字4、 关键字5 项目介绍 欢迎来到我们的 QML & C 项目&#xff01;这个项目结合了 QML…

onlyoffice在线预览加载优化

onlyoffice在线预览加载优化 onlyoffice版本&#xff1a;linux docker版本 问题&#xff1a; onlyoffice在线预览时会加载相关连的样式和js等静态文件&#xff0c;部分文件体积较大&#xff08;如sdk文件、fonts文件等&#xff09;导致前端加载缓慢 方法1&#xff1a;将大体…

围绕chatGPT的商业机会、商业点子独家分享。

本文概述 大鹏展翅亦须风势,热爱技术的你是否在等待一个绝佳的机会? chatGPT必将颠覆目前的软件形态、龙头企业。 这可能是我们这辈子最好的机会了! 何不乘风而起,抟扶摇而上者九万里! 本文主要展开想象,介绍围绕着chatGPT这种大语言模型最有价值、最有趣的创新项目,进…

etcd问题

一、etcd警告 "应用条目耗时过长 "是什么意思? 在大多数etcd成员同意提交请求后,每个etcd服务器将请求应用于其数据存储,并将结果持久化到磁盘。即使是慢速的机械磁盘或虚拟化的网络磁盘,如亚马逊的EBS或谷歌的PD,应用一个请求的时间通常应少于50毫秒。如果平均…