当前位置: 首页 > 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;需要把后…...

掌握MEAN.JS模块化开发:5个核心模块实战指南与最佳实践

掌握MEAN.JS模块化开发&#xff1a;5个核心模块实战指南与最佳实践 【免费下载链接】mean MEAN.JS - Full-Stack JavaScript Using MongoDB, Express, AngularJS, and Node.js - 项目地址: https://gitcode.com/gh_mirrors/mea/mean MEAN.JS作为基于MongoDB、Express、…...

遥感影像处理避坑指南:为什么你的SHP裁剪总失败?ArcMap与ENVI协作全解析

遥感影像裁剪实战避坑手册&#xff1a;从坐标系校准到多工具协同 当你在深夜盯着屏幕上那个扭曲变形的裁剪结果时&#xff0c;是否曾怀疑过人生&#xff1f;遥感影像的矢量裁剪看似简单&#xff0c;实则暗藏玄机。本文将带你深入剖析那些教科书上不会告诉你的实战细节&#xff…...

坚果云官方 Zotero 插件实测体验(完美适配 Zotero 7/8)

天下科研苦“文献同步”久矣&#xff01;如果你一直在用 Zotero 坚果云 WebDAV 方案&#xff0c;那你大概率踩过这些坑&#xff1a;❌ 繁琐的配置&#xff1a;要去网页端找入口、加应用、生成密码、再复制一长串服务器地址。❌ 频发 429 报错&#xff1a;同步文件一多&#xf…...

Python异步编程新选择:用Channels替代Celery实现实时消息推送(Django 3.2+演示)

Python异步编程新选择&#xff1a;用Channels替代Celery实现实时消息推送&#xff08;Django 3.2演示&#xff09; 当你的Django应用需要处理实时消息推送时&#xff0c;传统的CeleryWebhook方案可能已经无法满足你对低延迟的需求。本文将带你探索如何利用Django Channels和Web…...

Minecraft 1.12.2 彩色渐变字体模组:打造个性化聊天与物品命名

1. RGB Chat模组&#xff1a;让你的Minecraft文字绚丽多彩 还在用单调的白色文字聊天吗&#xff1f;RGB Chat模组彻底改变了Minecraft 1.12.2版本的文字显示方式。这个轻量级模组只有几百KB大小&#xff0c;却能给你的游戏体验带来质的飞跃。我第一次在服务器里看到彩色渐变文字…...

保姆级教程:手把手教你本地部署Qwen2.5-7B-Instruct旗舰模型

保姆级教程&#xff1a;手把手教你本地部署Qwen2.5-7B-Instruct旗舰模型 1. 前言&#xff1a;为什么选择Qwen2.5-7B-Instruct Qwen2.5-7B-Instruct是阿里通义千问团队在2024年9月发布的最新旗舰级开源大语言模型。相比轻量级的1.5B/3B版本&#xff0c;7B参数规模带来了质的飞…...

sklearn Pipeline:特征工程和建模流水线

你一定写过这样的代码&#xff1a;先对年龄做分箱&#xff0c;再对职业做 one-hot&#xff0c;然后把处理好的列拼起来&#xff0c;最后喂给模型。每一步都是散装的 fit_transform&#xff0c;变量名从 X_binned 到 X_encoded 到 X_final&#xff0c;稍不留神就在测试集上用了训…...

OCS2与Pinocchio联调避坑指南:如何让机械臂MPC求解速度提升3倍?

OCS2与Pinocchio联调避坑指南&#xff1a;如何让机械臂MPC求解速度提升3倍&#xff1f; 在工业机械臂控制领域&#xff0c;实时模型预测控制&#xff08;MPC&#xff09;的求解效率直接决定了系统的响应速度与稳定性。OCS2作为ETH Zurich开发的高性能MPC求解器&#xff0c;结合…...

暗黑破坏神2终极单机插件:PlugY生存工具包完全指南

暗黑破坏神2终极单机插件&#xff1a;PlugY生存工具包完全指南 【免费下载链接】PlugY PlugY, The Survival Kit - Plug-in for Diablo II Lord of Destruction 项目地址: https://gitcode.com/gh_mirrors/pl/PlugY 如果你是一名暗黑破坏神2的单机玩家&#xff0c;是否曾…...

STM32+FreeRTOS双分区开发避坑指南:Bootloader跳转前别忘了这行关键代码

STM32FreeRTOS双分区开发避坑指南&#xff1a;Bootloader跳转前别忘了这行关键代码 当你在STM32上实现BootloaderApp双分区架构时&#xff0c;是否遇到过这样的场景&#xff1a;Bootloader明明成功跳转到了应用程序&#xff0c;却在启动FreeRTOS调度器时突然崩溃&#xff1f;寄…...