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

236、二叉树的最近公共祖先

前提:

  • 所有 Node.val 互不相同 。
  • p != q
  • p 和 q 均存在于给定的二叉树中。

代码如下:

class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (root == q || root == p || root == NULL) return root;TreeNode* left = lowestCommonAncestor(root->left, p, q);TreeNode* right = lowestCommonAncestor(root->right, p, q);if (left != NULL && right != NULL) return root;if (left == NULL && right != NULL) return right;else if (left != NULL && right == NULL) return left;else  { //  (left == NULL && right == NULL)return NULL;}}
};

注意点:

  1. 求最小公共祖先,需要从底向上遍历,那么二叉树,只能通过后序遍历(即:回溯)实现从底向上的遍历方式。

  2. 在回溯的过程中,必然要遍历整棵二叉树,即使已经找到结果了,依然要把其他节点遍历完,因为要使用递归函数的返回值(也就是代码中的left和right)做逻辑判断。

  3. 要理解如果返回值left为空,right不为空为什么要返回right,为什么可以用返回right传给上一层结果。

形象化表示就是从root节点开始派出左右两个侦察兵,先判断他们是不是目标值,如果不是就让他们各自在探查自己的左右两个侦察兵是不是,不是就接着递归,直到有一个找到了目标值,就将找到这个目标值的侦察兵的信息记录一层一层传递回来,若有一个节点的左右侦察兵同时接到了探查信息,就将这个节点逐级返回。

相关文章:

236、二叉树的最近公共祖先

前提: 所有 Node.val 互不相同 。p ! qp 和 q 均存在于给定的二叉树中。 代码如下: class Solution { public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (root q || root p || root NULL) return root;TreeN…...

WebStorm 2024 for Mac JavaScript前端开发工具

Mac分享吧 文章目录 效果一、下载软件二、开始安装1、双击运行软件(适合自己的M芯片版或Intel芯片版),将其从左侧拖入右侧文件夹中,等待安装完毕2、应用程序显示软件图标,表示安装成功3、打开访达,点击【文…...

【Redis7】零基础篇

1 课程概述 2 Redis入门概述 2.1 是什么 Redis是基于内存的KV键值对内存数据库 Redis:Remote Dictionary Server(远程字典服务)是完全开源的,使用ANSIC语言编写遵守BSD协议,是一个高性能的Key-Value数据库提供了丰富的数据结构&#xff0c…...

[ROS 系列学习教程] 建模与仿真 - 使用 ros_control 控制差速轮式机器人

ROS 系列学习教程(总目录) 本文目录 一、差速轮式机器人二、差速驱动机器人运动学模型三、对外接口3.1 输入接口3.2 输出接口 四、控制器参数五、配置控制器参数六、编写硬件抽象接口七、控制机器人移动八、源码 ros_control 提供了多种控制器,其中 diff_drive_cont…...

Ubuntu22.04使用Systemd设置ROS 2开机自启动遇到的问题

在查找网上的各种开机自启动资料配置好开机自启动后,使用ros2 topic list不能显示话题。 1、问题解决:用户问题与domenID问题2、ROS2开机自启动服务教程3、多个ROS2开机自启动服务教程 1、问题解决:用户问题与domenID问题 在root用户下能看到…...

AI安全研究滞后?清华专家团来支招

在21世纪的科技浪潮中,人工智能(AI)无疑是最为耀眼的一抹亮色。随着技术的不断突破,AI正以前所未有的速度融入我们的日常生活,重塑着社会、经济乃至人类文明的面貌。然而,在这股汹涌澎湃的发展洪流中&#…...

12寸FAB 信息部内外工作职责的一些划分构思

FAB的信息部,也常被称为IT部门或信息化部门,承担着确保整个制造工厂的信息技术系统高效、安全运行的职责。以下是 一、FAB信息部的一些关键部门职责: 1. 战略规划:制定和实施信息技术战略,以支持FAB的长期业务目标和增…...

css做旋转星球可举一反三

<!DOCTYPE html> <html lang"en"><head> <meta charset"UTF-8" /> <title>旋转的星球</title> <style type"text/css">.box {/*position: relative;*/position: absolute;width: 139px;height: 139p…...

AcWing 1256:扩展二叉树

【题目来源】https://www.acwing.com/problem/content/1258/【题目描述】 由于先序、中序和后序序列中的任一个都不能唯一确定一棵二叉树&#xff0c;所以对二叉树做如下处理&#xff0c;将二叉树的空结点用 补齐&#xff0c;如图所示。 我们把这样处理后的二叉树称为原二叉树…...

三维家:SaaS的IT规模化降本之道|OceanBase 《DB大咖说》(十一)

OceanBase《DB大咖说》第 11 期&#xff0c;我们邀请到了三维家的技术总监庄建超&#xff0c;来分享他对数据库技术的理解&#xff0c;以及典型 SaaS 场景在数据库如何实现规模化降本的经验与体会。 庄建超&#xff0c;身为三维家的技术总监&#xff0c;独挑大梁&#xff0c;负…...

ai智能语音机器人是如何影响客户体验的?电销机器人部署

随着人工智能技术的进步&#xff0c;越来越多的企业在寻求如何将人工智能技术融合到现有的商业模式上&#xff0c;进而实现自动化、智能化。在通信行业大量使用智能语音机器人、聊天机器人、客服机器人时&#xff0c;它能和“客户体验”并驾齐驱吗&#xff0c;还是可以让客户体…...

vue3使用v-html实现文本关键词变色

首先看应用场景 这有一段文本内容&#xff0c;是项目的简介&#xff0c;想要实现将文本中的关键词进行变色处理 有如下关键词 实现思路 遍历文本内容&#xff0c;找到关键词&#xff0c;并使用某种方法更改其字体样式。经过搜寻资料决定采用v-html实现&#xff0c;但是v-h…...

C#面:举列 a=10,b=15,在不用第三方变量的前提下,把a,b的值互换

要在不使用第三方变量的前提下交换a和b的值&#xff0c;可以使用异或运算。异或运算的特性是&#xff0c;对于两个相同的数进行异或运算&#xff0c;结果为0&#xff1b;对于任意数与0进行异或运算&#xff0c;结果为该数本身。因此&#xff0c;可以通过多次异或运算来实现变量…...

编写动态库

1.创建库.c .h文件 2.编写Makefile文件 3.make之后形成.so文件 4.make output,形成mylib 5.把mylib拷贝到test里面 mv mylib /test 6.编译 gcc main.c -I mylib/include -L mylib/lib -lmymethod形成a.out 但是直接执行会出现以下问题 很显然没有找到动态库 7.解决加载找不…...

记一次阿里云服务器java应用无法响应且无法远程连接的问题排查

问题表现 java服务无响应&#xff0c;无法远程链接到服务器。 今天中午12点多&#xff0c;应用直接崩溃。后续进入到服务器&#xff0c;发现java进程都不在了&#xff0c; 排查过程 先安装atop工具 安装、配置并使用atop监控工具 等下次再出现时看相关时间点日志&#xff…...

雷池WAF+Modsecurity安装防护及系统加固

君衍. 一、雷池WAF1、什么是雷池2、什么是WAF3、雷池的功能4、WAF部署架构5、整体检测流程 二、雷池WAF环境依赖1、查看本地CPU架构2、Docker安装2.1 卸载旧版本2.2 安装yum-utils工具包2.3 设置镜像仓库2.4 安装docker2.5 启动docker并查看版本 3、Docker Compose安装3.1 卸载…...

【Python】已解决:SyntaxError: positional argument follows keyword argument

文章目录 一、分析问题背景二、可能出错的原因三、错误代码示例四、正确代码示例五、注意事项 已解决&#xff1a;SyntaxError: positional argument follows keyword argument 一、分析问题背景 在Python编程中&#xff0c;当我们在调用函数时混合使用位置参数&#xff08;p…...

leetcode-20-回溯-切割、子集

一、[131]分割回文串 给定一个字符串 s&#xff0c;将 s 分割成一些子串&#xff0c;使每个子串都是回文串。 返回 s 所有可能的分割方案。 示例: 输入: "aab" 输出: [ ["aa","b"], ["a","a","b"] ] 分析&…...

利用深度学习模型进行语音障碍自动评估

语音的产生涉及器官的复杂协调&#xff0c;因此&#xff0c;语音包含了有关身体各个方面的信息&#xff0c;从认知状态和心理状态到呼吸条件。近十年来&#xff0c;研究者致力于发现和利用语音生物标志物——即与特定疾病相关的语音特征&#xff0c;用于诊断。随着人工智能&…...

TP8 JS(html2canvas) 把DIV内容生成二维码并与背景图、文字组合生成分享海报

方法一&#xff1a;前端JS生成(推荐) 注意&#xff1a; 1.这个网页只能截图图片效果代码&#xff0c;其它任何html效果都不能有&#xff0c;不然截图就不准确 2.如果要生成的图片DIV内容中引用了第三个方的图片&#xff0c;就是不使用同一个域名下的图片&#xff0c;需要把后…...

【计算机网络工程论文】基于三层交换的局域网设计:连平中学教学楼VLAN划分与eNSP仿真应用

摘 要 随着连平中学发展和信息化平台的建设&#xff0c;面对庞大的信息数据和高要求的管理效率&#xff0c;网络的规划、管理、安全逐渐成为关键。对教学楼而言&#xff0c;规划一个高效、稳定、可扩展的局域网至关重要。 本文针对连平中学教学单位&#xff0c;鉴于其所有部门…...

Phi-4-mini-reasoning企业落地案例:集成至内部知识库的逻辑问答模块

Phi-4-mini-reasoning企业落地案例&#xff1a;集成至内部知识库的逻辑问答模块 1. 项目背景与需求 企业内部知识库系统通常面临一个共同挑战&#xff1a;员工在查找专业问题时&#xff0c;往往需要花费大量时间筛选信息&#xff0c;特别是涉及数学计算、逻辑推理等需要多步分…...

【DeepSeek-R1背后的技术】系列七:冷启动——从“零”到“一”的智能启蒙

1. 冷启动&#xff1a;AI模型的"启蒙教育" 想象一下&#xff0c;你面前站着一个刚出生的婴儿&#xff0c;他对这个世界一无所知。如果你直接把他扔进大学课堂&#xff0c;会发生什么&#xff1f;他可能会哭闹、听不懂任何内容&#xff0c;甚至产生恐惧心理。这就是一…...

09. CSS生成艺术创作指南:用代码绘制视觉诗篇

09. CSS生成艺术创作指南&#xff1a;用代码绘制视觉诗篇 引言 CSS 不仅仅是样式语言&#xff0c;它也是一种创作艺术的工具。通过 CSS&#xff0c;我们可以创建出令人惊叹的生成艺术作品&#xff0c;这些作品不仅美观&#xff0c;而且具有动态性和交互性。作为一名把代码当散文…...

MATLAB图像处理实战:5分钟搞定腐蚀膨胀操作(附完整代码)

MATLAB图像形态学处理实战&#xff1a;从原理到代码实现 在数字图像处理领域&#xff0c;形态学操作就像一把精密的"手术刀"&#xff0c;能够对图像进行精细的"雕刻"和"修饰"。无论是去除噪点、填补空洞&#xff0c;还是分离粘连物体&#xff0c…...

保姆级避坑指南:在Windows上用VirtualBox 6.0.24跑Ubuntu,从开机报错到完美显示的完整流程

从开机报错到完美显示&#xff1a;VirtualBox 6.0.24运行Ubuntu全流程实战手册 当你第一次在Windows上用VirtualBox启动Ubuntu虚拟机时&#xff0c;那个刺眼的报错提示可能会让你措手不及。别担心&#xff0c;这几乎是每个虚拟化新手都会经历的"成人礼"。本文将带你完…...

C++并发编程实战:std::atomic的exchange与compare_exchange操作到底怎么选?

C并发编程实战&#xff1a;std::atomic的exchange与compare_exchange操作到底怎么选&#xff1f; 在构建高性能并发系统时&#xff0c;开发者常面临一个关键抉择&#xff1a;当需要原子更新共享数据时&#xff0c;究竟该选择exchange、compare_exchange_weak还是compare_exchan…...

手写 Vue3 自定义指令:防抖、点击外部、权限控制

在 Vue3 开发中&#xff0c;指令&#xff08;Directive&#xff09;是一个非常实用的特性&#xff0c;它允许我们在 DOM 元素上添加自定义行为&#xff0c;封装可复用的逻辑。Vue3 内置了 v-model、v-show、v-bind 等常用指令&#xff0c;但在实际开发中&#xff0c;我们经常会…...

银发健康消费“新战场”:线下渠道红利期开启,10+嘉宾重磅分享实战方法论

​银发经济与连锁药店转型的双向奔赴整理 | AgeClub内容团队前言当前&#xff0c;中国银发经济已成为国内增长最快的赛道之一。数据显示&#xff0c;我国银发经济市场规模已突破 10 万亿元&#xff0c;未来整体规模有望超过 30 万亿元。精准对接优质渠道&#xff0c;成为众多银…...

从‘它又挂了’到‘稳如老狗’:我是如何用Prometheus+Grafana给自家小破站做监控的

从“它又挂了”到“稳如老狗”&#xff1a;我是如何用PrometheusGrafana给自家小破站做监控的 凌晨三点&#xff0c;手机突然响起钉钉告警——这已经是本周第三次被“502 Bad Gateway”的提示音吵醒。揉着惺忪睡眼重启Nginx时&#xff0c;我突然意识到&#xff1a;这个用业余时…...