首页/新闻资讯/正文详情

二叉树的最近公共祖先(以及二叉搜索树)

发布时间:2026/9/27 7:10:57 来源:云帆数科 栏目:资讯中心
二叉树的最近公共祖先(以及二叉搜索树)
自底向上怎么办回溯啊都是递归从上向下和从下向上有什么区别代码可视化自顶向下处理(root); go(root-left); go(root-right);自底向上go(root-left); go(root-right); 处理(root);如果找到一个节点发现左子树出现结点p右子树出现节点q或者 左子树出现结点q右子树出现节点p那么该节点就是节点p和q的最近公共祖先。遇见p就回溯遇见q也回溯如果返回值两边同时不为空那这个节点就是要找的节点。遇到 q 或者 p 就返回这样也包含了 q 或者 p 本身就是 公共祖先的情况。递归三部曲确定递归函数返回值以及参数需要递归函数返回值来告诉我们是否找到节点q或者p那么返回值为bool类型就可以了。但我们还要返回最近公共节点可以利用上题目中返回值是TreeNode * 那么如果遇到p或者q就把q或者p返回返回值不为空就说明找到了q或者p。代码如下TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)确定终止条件遇到空的话因为树都是空了所以返回空。那么我们来说一说如果 root q或者 root p说明找到 q p 则将其返回这个返回值后面在中节点的处理过程中会用到那么中节点的处理逻辑下面讲解。代码如下if (root q || root p || root NULL) return root;确定单层递归逻辑虽然我的递归函数有返回值比如返回找到的节点指针但我不能像查字典那样找到就立刻返回。我必须先把左子树的返回值看看再把右子树的返回值看看根据两边的情况综合判断最后再决定返回什么。举个“有返回值但依然全遍历”的代码骨架LCATreeNode* find(TreeNode* root, TreeNode* p, TreeNode* q) { if (!root || root p || root q) return root; // ① 我先去左边找并不直接返回 TreeNode* left find(root-left, p, q); // ② 我再必须去右边找这就是全遍历 TreeNode* right find(root-right, p, q); // ③ 走完两边了我才根据结果做决策 if (left right) return root; // 两边都找到了当前就是祖先 return left ? left : right; // 哪边找到了就返回哪边 }这里虽然有返回值TreeNode*但你看第 ① 和第 ② 步它并没有在第 ① 步找到东西后就return而是先存起来继续去执行第 ② 步。这就强制程序把左、右子树全部遍历完。看逻辑就看代码随想录吧。我觉得可以把这道题背下来不难。但是现在其实我已经理解了就是1.先判断一下返回什么例如上图65null都要返回。2.递归找left和right3.分别判断left和right找到了返回root没找到返回什么的情况。那如果是二叉搜索树呢特别简单不用使用回溯二叉搜索树自带方向性可以方便的从上向下查找目标区间遇到目标区间内的节点直接返回。迭代即可。都大于就去左边都小于就去右边要么就返回root出循环了就返回nullclass Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { while(root){ if(root-valq-valroot-valp-val){ rootroot-left; } else if(root-valq-valroot-valp-val){//这里要用else如果只用if的话在一环root变化之后还会在这里再判断一次进入第一个 ifroot 被更新为左孩子。然后程序继续执行第二个 if此时 root 已经改变可能会错误地进入第二个分支 rootroot-right; } else return root; } return NULL; } };

相关推荐

AI Movie Buddy:个人影视智能体的架构与实践
AI Movie Buddy:个人影视智能体的架构与实践

1. 这不是科幻预告片,而是我们正在调试的日常现实“Will we soon have our own personal AI Movie Buddy?”——这个标题乍看像科技媒体抛出的一个开放式提问,但在我过去三年深度参与影视AI工具链搭建、为十几家内容工作室做智能剪辑辅助系统落地的过程… · 2026/9/17 10:56:14

我发现别人博客的字要比我多
我发现别人博客的字要比我多

我按照第5,15,25,35,45,55,65,75,85,95名次的顺序看了10个博主,发现他们博客的字要比我多一点。也就差不多是我博客字数的二十倍那么多。我才写这么几个字就有… · 2026/8/22 9:38:43

2026经济周期转折与产业赛道更迭分析
2026经济周期转折与产业赛道更迭分析

1. 2026年经济周期的关键转折特征2026年将呈现典型的"新旧动能转换"经济特征。从周期理论看,这可能是朱格拉周期(设备投资周期)与基钦周期(库存周期)的叠加拐点。根据近三十年经济数据回溯,这种双… · 2026/9/21 5:09:26

3个实战案例解决wordpress页面重定向循环
3个实战案例解决wordpress页面重定向循环

3个实战案例解决wordpress页面重定向循环 域名解析指向了服务器IP,服务器却把请求踢回域名,这个死循环一卡,网站直接白屏。很多项目经理接手烂摊子时,面对后台日志里满屏的301和302跳转,脑子里只剩“域名服务器搞不懂”这几个字。别慌… · 2026/9/27 7:10:42

DeerFlow Docker Desktop 部署教程
DeerFlow Docker Desktop 部署教程

文章目录DeerFlow Docker Desktop 部署教程1 准备2 下载官方仓库3 把两个示例配置改名(关键步骤)4 编辑 config.yaml 填模型5 创建 .env 环境变量文件6 用 Docker Desktop 启动7 验证DeerFlow Docker Desktop 部署教程 核心思路:下载官方仓库… · 2026/9/27 7:10:36

Laravel Lang 保加利亚语(bg)翻译状态深度解读:缺失清单、来源定位与补全实践
Laravel Lang 保加利亚语(bg)翻译状态深度解读:缺失清单、来源定位与补全实践

后端 【免费下载链接】lang List of 128 languages for Laravel Framework, Laravel Jetstream, Laravel Fortify, Laravel Breeze, Laravel Cashier, Laravel Nova and Laravel UI. 项目地址: https://gitcode.com/gh_mirrors/la/lang 点击查看 免费下载 导读 本… · 2026/9/27 7:10:36

Microsoft Agent Framework 中 Agent 的架构形态
Microsoft Agent Framework 中 Agent 的架构形态

目录 1. 应用托管型 Agent(Application-owned Agent) 可用的模型提供商 不同 Model Provider 面向 Microsoft Agent Framework 提供的能力 .NET SDK 和 Endpoint 2. 自定义实现型 Agent(Custom Agent) 引用 Abstractions 包… · 2026/9/27 7:10:36

Texture 布局引擎深入解析:从 ASLayoutSpec 到 UIKit 渲染的完整流程
Texture 布局引擎深入解析:从 ASLayoutSpec 到 UIKit 渲染的完整流程

移动开发UI组件 【免费下载链接】Texture Smooth asynchronous user interfaces for iOS apps. 项目地址: https://gitcode.com/gh_mirrors/te/Texture 点击查看 免费下载 导读 本篇技术指南以 Texture(AsyncDisplayKit)官方开发文档《Layo… · 2026/9/27 7:10:36

Model-Optimizer 投机解码实战指南:用 Medusa 与 EAGLE 将 LLM 推理延迟降至最低
Model-Optimizer 投机解码实战指南:用 Medusa 与 EAGLE 将 LLM 推理延迟降至最低

人工智能大模型模型优化模型量化模型压缩 【免费下载链接】Model-Optimizer A unified library of SOTA model optimization techniques like quantization, distillation, pruning, neural architecture search, speculative decoding, etc. It compresses deep learning mode… · 2026/9/27 7:10:29

MATLAB雷达信号脉冲压缩仿真:LFM线性调频、匹配滤波与距离分辨率实现
MATLAB雷达信号脉冲压缩仿真:LFM线性调频、匹配滤波与距离分辨率实现

简介:这套Matlab仿真工具完整呈现雷达信号脉冲压缩过程,从线性调频(LFM)信号生成、目标回波仿真到匹配滤波压缩处理均有可运行代码支撑,面向电子信息工程、计算机、数学等专业学生,适用于课程设计、期末大作… · 2026/9/27 0:00:01

汕头网站建设制作厂家避坑指南:5大注意事项救急
汕头网站建设制作厂家避坑指南:5大注意事项救急

汕头网站建设制作厂家避坑指南:5大注意事项救急 改个需求建站公司拖一周,这种憋屈事我见得太多了。 很多汕头老板找本地建站团队,签合同前看着方案挺美,一上线就变脸。 今天不聊虚的,直接拆解找 汕头网站建设制作厂家 时的5个核心 注意事项… · 2026/9/27 0:00:01

多模态虚假新闻检测实战:BERT+ResNet双塔与对比学习
多模态虚假新闻检测实战:BERT+ResNet双塔与对比学习

简介:基于PyTorch的多模态虚假新闻检测项目完整代码包,面向自然语言处理与计算机视觉交叉方向的开发者、科研人员及毕业设计选题者,解决社交媒体中文本与图像联合识别虚假新闻的问题。系统以BERT预训练模型提取文本语义特征,以Res… · 2026/9/27 0:00:01

MATLAB雷达信号脉冲压缩仿真:LFM线性调频、匹配滤波与距离分辨率实现
MATLAB雷达信号脉冲压缩仿真:LFM线性调频、匹配滤波与距离分辨率实现

简介:这套Matlab仿真工具完整呈现雷达信号脉冲压缩过程,从线性调频(LFM)信号生成、目标回波仿真到匹配滤波压缩处理均有可运行代码支撑,面向电子信息工程、计算机、数学等专业学生,适用于课程设计、期末大作… · 2026/9/27 0:00:01

汕头网站建设制作厂家避坑指南:5大注意事项救急
汕头网站建设制作厂家避坑指南:5大注意事项救急

汕头网站建设制作厂家避坑指南:5大注意事项救急 改个需求建站公司拖一周,这种憋屈事我见得太多了。 很多汕头老板找本地建站团队,签合同前看着方案挺美,一上线就变脸。 今天不聊虚的,直接拆解找 汕头网站建设制作厂家 时的5个核心 注意事项… · 2026/9/27 0:00:01

多模态虚假新闻检测实战:BERT+ResNet双塔与对比学习
多模态虚假新闻检测实战:BERT+ResNet双塔与对比学习

简介:基于PyTorch的多模态虚假新闻检测项目完整代码包,面向自然语言处理与计算机视觉交叉方向的开发者、科研人员及毕业设计选题者,解决社交媒体中文本与图像联合识别虚假新闻的问题。系统以BERT预训练模型提取文本语义特征,以Res… · 2026/9/27 0:00:01

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码