当前位置: 首页 > news >正文

【LeetCode-中等题】236. 二叉树的最近公共祖先

文章目录

    • 题目
    • 方法一:后序遍历 + 回溯

题目

在这里插入图片描述

方法一:后序遍历 + 回溯

解题的核心就是:采用后序遍历

  1. 讨论p,q是否在当前的root的两边,如在两边则返回当前节点root

在这里插入图片描述

  1. 如何不在两边,只要出现一个节点等于p或者q就返回当前节点
    在这里插入图片描述
// 后序遍历  + 回溯public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root == null) return null;//即做节点判空条件、、也做递归出口 (说明递归到null  都没有找到  p或q)if(root == p || root == q)  return root;//  说明(当前要递归的节点就是p或q直接返回)或递归找到了p或q  就不用再往下递归了 结束此次递归  返回 p 或 qTreeNode left = lowestCommonAncestor(root.left,p,q);//递归左子树,返回值就是找到的p或q  没找到就是nullTreeNode right = lowestCommonAncestor(root.right,p,q);//递归右子树返回值就是找到的p或q  没找到就是nullif(left!=null  && right!=null) return root;// 如果遍历左右子树 在左子树或右子树找到了都找到了(  p  或  q  )//  说明当前结点就是  p  q  的最近公共祖先if(left != null && right == null) return left;//如果当前遍历左右子树结点只找到  一个 (q 或者 p)//说明下一个p或者q其实就是在这个结点下面 因为一旦找到了p 或q就不会往下遍历了,// 所以一旦出现只能找到一个(q  或  p)的情况 说明这个这个节点即是(p 或 q) 又是q 和 p 的最近公共祖先if(right != null && left==null) return right; return null;//所有都不满足直接返回null}

二叉树的最近公共祖先(DFS ,清晰图解)

相关文章:

【LeetCode-中等题】236. 二叉树的最近公共祖先

文章目录 题目方法一:后序遍历 回溯 题目 方法一:后序遍历 回溯 解题的核心就是:采用后序遍历 讨论p,q是否在当前的root的两边,如在两边则返回当前节点root 如何不在两边,只要出现一个节点等于p或者q就…...

如何拼接两个视频在一起?

如何拼接两个视频在一起?在度过一个美好周末的时候,我和朋友一起拍摄了两组视频,准备将两个视频合并成一个并发布到朋友圈。这个想法非常棒,但是我在第一步就遇到了麻烦:如何将这两个视频拼接在一起?这听起…...

Programming abstractions in C阅读笔记:p130-p131

《Programming Abstractions In C》学习第52天,p130-p131,总结如下: 一、技术总结 1. pig latin game 通过pig latin game掌握字符复制,指针遍历等操作。 /** 输入:字符串,这里采用书中坐着自定义的get…...

如何在Windows本地快速搭建SFTP文件服务器,并通过端口映射实现公网远程访问

文章目录 1. 搭建SFTP服务器1.1 下载 freesshd服务器软件1.3 启动SFTP服务1.4 添加用户1.5 保存所有配置 2 安装SFTP客户端FileZilla测试2.1 配置一个本地SFTP站点2.2 内网连接测试成功 3 使用cpolar内网穿透3.1 创建SFTP隧道3.2 查看在线隧道列表 4. 使用SFTP客户端&#xff0…...

C#---第二十:不同类型方法的执行顺序(new / virtual / common / override)

本文介绍不同类型的方法,在代码中的执行顺序问题: 构造方法普通方法(暂用common代替)、虚方法(Virtual修饰)、New方法(new修饰)三个优先级相同overide方法(会替换virtual…...

lnmp架构-PHP

08 PHP源码编译 09 php初始化配置 nginx 的并发能力强 phpinfo函数 就是 显示php信息 10 php的功能模块 编译memcache模块 php的动态模块方式 mamcache 就是内存 直接从内存中命中 所以性能非常好 但是 这还不是最好的方式 工作流程 关键看后端的 php 什么时候处理完 mamcac…...

【javascript实操记录】

功能描述: 1. 利用split()方法对测试数据进行解析:学科,日期 2. 将测试数据封装成对象数组的格式 3. 使用数组的sort()方法和Date对象,将测试数据按照日期从早到晚进行排序 4. 表格数据的静态填充 5. 距离最近考试的倒计时天…...

Mysql--技术文档--悲观锁、乐观锁-《控制并发机制简单认知、深度理解》

阿丹: 首先在谈到并发控制机制的时候,我们通常会提及两种重要的锁策略。悲观锁(Pessimistic Locking)和乐观锁(Optimistic Locking)。这两个是在处理并发的时候采取的不同思路。 悲观锁: 悲观锁…...

【GO】LGTM_Grafana_Tempo(2)_官方用例改后实操

最近在尝试用 LGTM 来实现 Go 微服务的可观测性,就顺便整理一下文档。 Tempo 会分为 4 篇文章: Tempo 的架构官网测试实操跑通gin 框架发送 trace 数据到 tempogo-zero 微服务框架使用发送数据到 tempo 根据官方文档实操跑起来 tempo,中间根…...

git 口令

把当前目录变成 Git 可以管理的仓库: git init 下载一个项目和它的整个代码历史 git clone [url] 切换到 develop 分支: git checkout develop 建立并切换到 new 分支 git checkout -b new 查看所有分支: git branch -a 删除 tese …...

【回眸】剑指offer(二)解题思路

题解 | #数字在升序数组中出现的次数# JZ3数字在升序数组中出现的次数 描述 给定一个长度为 n 的非降序数组和一个非负数整数 k ,要求统计 k 在数组中出现的次数 数据范围:0≤n≤1000,0≤k≤100,数组中每个元素的值满足 0≤val≤100 要求…...

Python 基本文件操作及os库

内置函数文件操作 python内置函数提供了简单的文件操作支持。 open() open()函数打开一个文件,创建一个file对象,相关的方法才可以调用它进行读写。 语法为: open(file,moder,buffering-1,encodingNone,errorsNone,newlineNone,closefdT…...

YOLOv5算法改进(9)— 替换主干网络之ShuffleNetV2

前言:Hello大家好,我是小哥谈。ShuffleNetV2 是一种轻量级的神经网络架构,适用于移动设备和嵌入式设备等资源受限的场景,旨在在计算资源有限的设备上提供高效的计算和推理能力,它通过引入通道重排操作和逐点组卷积来减…...

三、mycat分库分表

第五章 分库分表 一个数据库由很多表的构成,每个表对应着不同的业务,垂直切分是指按照业 务将表进行分类,分布到不同 的数据库上面,这样也就将数据或者说压力分担到不同 的库上面,如下图: 系统被切分成了&…...

gitlab提交项目Log in with Access Token错误

目录 报错信息 问题描述 解决方案 报错信息 问题描述 在提交项目到gitlab时,需要添加账户信息 ,但是报了这样一个错,原因应该就是路径问题,我在填写server地址的时候,就出现了路径问题,我把多余的几个/…...

openGauss学习笔记-56 openGauss 高级特性-DCF

文章目录 openGauss学习笔记-56 openGauss 高级特性-DCF56.1 架构介绍56.2 功能介绍56.3 使用示例 openGauss学习笔记-56 openGauss 高级特性-DCF DCF全称是Distributed Consensus Framework,即分布式一致性共识框架。DCF实现了Paxos、Raft等解决分布式一致性问题典…...

Xcode 14 pod init报错

文章目录 1.报错2.解决方法(本人亲测有效) 1.报错 [!] Oh no, an error occurred. Search for existing GitHub issues similar to yours: https://github.com/CocoaPods/CocoaPods/search?q%5BXcodeproj%5DUnknownobjectversion%2856%29.&typeIs…...

飞腾PSPA可信启动--2 数字签名证书

今天继续第二章,数字签名证书的介绍。 此章节录制了讲解视频,可以在B站进行观看:...

微前端:重塑大型项目的前沿技术

引言 随着互联网技术的飞速发展,前端开发已经从简单的页面制作逐渐转变为复杂的应用开发。在这个过程中,传统的前端开发模式已经难以满足大型项目的需求。微前端作为一种新的前端架构模式,应运而生,它旨在解决大型项目中的前端开…...

官方推荐使用的OkHttp4网络请求库全面解析(Android篇)

作者:cofbro 前言 现在谈起网络请求,大家肯定下意识想到的就是 okhttp 或者 retrofit 这样的三方请求库。诚然,现在有越来越多的三方库帮助着我们快速开发,但是对于现在的程序员来说,我们不仅要学会如何去用&#xff…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时,需结合业务场景设计数据流转链路,重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点: 一、核心对接场景与目标 商品数据同步 场景:将1688商品信息…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句,它能够让用户直接在浏览器内练习SQL的语法,不需要安装任何软件。 链接如下: sqliteviz 注意: 在转写SQL语法时,关键字之间有一个特定的顺序,这个顺序会影响到…...

vue3 定时器-定义全局方法 vue+ts

1.创建ts文件 路径&#xff1a;src/utils/timer.ts 完整代码&#xff1a; import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

uniapp微信小程序视频实时流+pc端预览方案

方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度​WebSocket图片帧​定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐​RTMP推流​TRTC/即构SDK推流❌ 付费方案 &#xff08;部分有免费额度&#x…...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/

使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题&#xff1a;docker pull 失败 网络不同&#xff0c;需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

CMake控制VS2022项目文件分组

我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...

C# 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

佰力博科技与您探讨热释电测量的几种方法

热释电的测量主要涉及热释电系数的测定&#xff0c;这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中&#xff0c;积分电荷法最为常用&#xff0c;其原理是通过测量在电容器上积累的热释电电荷&#xff0c;从而确定热释电系数…...

Java数值运算常见陷阱与规避方法

整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...