【算法与数据结构】235、LeetCode二叉搜索树的最近公共祖先
文章目录
- 一、题目
- 二、解法
- 三、完整代码
所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。
一、题目
二、解法
思路分析:本题和这道题类似【算法与数据结构】236、LeetCode二叉树的最近公共祖先,相同的算法也能解这道题,但是没有充分利用到二叉搜索树的性质,二叉搜索树的性质为中间节点的键值大于所有左子树节点的键值,大于所有右子树的键值。因此要找到两个节点的最近祖先节点,只需要确定节点位于[p,q](或者是[q,p]大小未知,左闭右闭的区间)区间内。那么当节点键值比两个节点的键值都小时,说明公共最先节点在右子树内,遍历右子树即可,反之亦然,最终剩下的就是最近公共祖先节点。
程序如下:
class Solution {
public:// 后序遍历: 左右中// 1、输入参数TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {// 2、终止条件if (root == NULL) return root; // 如果节点相等或者是空节点返回// 3、单层递归逻辑if ((root->val > q->val && root->val > p->val)) {TreeNode* left = lowestCommonAncestor(root->left, p, q); // 左if (left != NULL) return left;}if ((root->val < q->val && root->val < p->val)) {TreeNode* right = lowestCommonAncestor(root->right, p, q); // 右if (right != NULL) return right;} return root;}
};
三、完整代码
# include <iostream>
# include <vector>
# include <string>
# include <queue>
using namespace std;// 树节点定义
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode() : val(0), left(nullptr), right(nullptr) {}TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};class Solution {
public:// 后序遍历: 左右中// 1、输入参数TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {// 2、终止条件if (root == NULL) return root; // 如果节点相等或者是空节点返回// 3、单层递归逻辑if ((root->val > q->val && root->val > p->val)) {TreeNode* left = lowestCommonAncestor(root->left, p, q); // 左if (left != NULL) return left;}if ((root->val < q->val && root->val < p->val)) {TreeNode* right = lowestCommonAncestor(root->right, p, q); // 右if (right != NULL) return right;} return root;}
};// 前序遍历迭代法创建二叉树,每次迭代将容器首元素弹出(弹出代码还可以再优化)
void Tree_Generator(vector<string>& t, TreeNode*& node) {if (!t.size() || t[0] == "NULL") return; // 退出条件else {node = new TreeNode(stoi(t[0].c_str())); // 中if (t.size()) {t.assign(t.begin() + 1, t.end());Tree_Generator(t, node->left); // 左}if (t.size()) {t.assign(t.begin() + 1, t.end());Tree_Generator(t, node->right); // 右}}
}template<typename T>
void my_print(T& v, const string msg)
{cout << msg << endl;for (class T::iterator it = v.begin(); it != v.end(); it++) {cout << *it << ' ';}cout << endl;
}template<class T1, class T2>
void my_print2(T1& v, const string str) {cout << str << endl;for (class T1::iterator vit = v.begin(); vit < v.end(); ++vit) {for (class T2::iterator it = (*vit).begin(); it < (*vit).end(); ++it) {cout << *it << ' ';}cout << endl;}
}// 层序遍历
vector<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);vector<vector<int>> result;while (!que.empty()) {int size = que.size(); // size必须固定, que.size()是不断变化的vector<int> vec;for (int i = 0; i < size; ++i) {TreeNode* node = que.front();que.pop();vec.push_back(node->val);if (node->left) que.push(node->left);if (node->right) que.push(node->right);}result.push_back(vec);}return result;
}// 前序遍历,找二叉树中指定的键值
TreeNode* traversal_preOrder(TreeNode* cur, int val) {if (cur == NULL) return NULL;if (cur->val == val) return cur; // 中if (traversal_preOrder(cur->left, val) != NULL) return traversal_preOrder(cur->left, val); // 左 if (traversal_preOrder(cur->right, val) != NULL) return traversal_preOrder(cur->right, val); // 右 return NULL;
}int main()
{// 构建二叉树vector<string> t = { "6", "2", "0", "NULL", "NULL", "4", "3", "NULL", "NULL", "5", "NULL", "NULL", "8", "7", "NULL", "NULL", "9", "NULL", "NULL" }; // 前序遍历my_print(t, "目标树");TreeNode* root = new TreeNode();Tree_Generator(t, root);vector<vector<int>> tree = levelOrder(root);my_print2<vector<vector<int>>, vector<int>>(tree, "目标树:");// 构建p, q节点int p = 2, q = 8;TreeNode* P_node = traversal_preOrder(root, p);TreeNode* Q_node = traversal_preOrder(root, q);// 找最近公共祖先节点Solution s;TreeNode* result = s.lowestCommonAncestor(root, P_node, Q_node);cout << "节点 " << P_node->val << " 和节点 " << Q_node->val << " 的最近公共祖先节点为 " << result->val << endl;system("pause");return 0;
}
end
相关文章:
【算法与数据结构】235、LeetCode二叉搜索树的最近公共祖先
文章目录 一、题目二、解法三、完整代码 所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析:本题和这道题类似【算法与数据结构】236、LeetCode二叉树的最近公共祖先,相同的算法也能解…...
bboss 流批一体化框架 与 数据采集 ETL
数据采集 ETL 与 流批一体化框架 特性: 高效、稳定、快速、安全 bboss 是一个基于开源协议 Apache License 发布的开源项目,主要由以下三部分构成: Elasticsearch Highlevel Java Restclient , 一个高性能高兼容性的Elasticsea…...
JVM详细教程
JVM 前言 还在完善中先发布 JVM虚拟机厂家多钟多样,具体实现细节可能不一样,这里主要讲的是虚拟机的规范,以下内容融合了各个平台发布的内容和周志明老师的《深入理解java虚拟机》 JVM概述 如何理解jvm跨平台? 编译成汇编代码…...
Smartbi吴华夫:后疫情时代,BI发展趋势的观察与应对
沿着旧地图找不到新大陆,“基于指标体系的可视化分析和增强分析”成为BI发展新阶段。Smartbi V11系列新品与时俱进,以指标为核心,同时融合BI应用,赋能管理者和业务,成为引领数字化运营的新航标! ——思迈特…...
软件设计模式系列之三———工厂方法模式
1 模式的定义 工厂方法模式是一种常见的设计模式,属于创建型设计模式之一,它在软件工程中用于对象的创建。该模式的主要思想是将对象的创建过程抽象化,将具体对象的实例化延迟到子类中完成,以便在不同情况下可以创建不同类型的对…...
pytorch 多卡分布式训练 调用all_gather_object 出现阻塞等待死锁的问题
pytorch 多卡分布式训练 torch._C._distributed_c10d中的函数all_gather_object 出现阻塞等待死锁的问题 解决办法就是 在进程通信之前调用torch.cuda.set_device(local_rank) For NCCL-based processed groups, internal tensor representations of objects must be moved …...
SpringMvc增删改查
SpringMvc增删改查 一、前期准备二、逆向生成增删改查2.2.aspect切面层2.3.Mybatis generator逆向生成2.4.根据生成代码编写Biz层与实现类 三、controller层代码编写四、前台代码与分页代码五、案例测试 一、前期准备 1.2.导入pom.xml依赖 <?xml version"1.0" …...
【计算机网络】网络编程接口 Socket API 解读(5)
Socket 是网络协议栈暴露给编程人员的 API,相比复杂的计算机网络协议,API 对关键操作和配置数据进行了抽象,简化了程序编程。 本文讲述的 socket 内容源自 Linux man。本文主要对各 API 进行详细介绍,从而更好的理解 socket 编程。…...
手动实现一个bind函数!
原文地址:手动实现一个bind函数! - 知乎 1.bind函数用法 bind()方法用于创建一个新的函数,这个新函数接收的第一个参数代表的就是this,利用bind()函数我就就可以任意改变函数内部的this指向了。 官网的解释: bind()…...
数据结构-时间复杂度/空间复杂度
Hello,好久没有更新了哦,已经开始学习数据结构了,这篇文章呢就是对刚学数据结构所接触到的时间复杂度进行一个分享哦,如果有错误之处,大家记得拍拍我哦~ 既然要讨论时间/空间复杂度,那我们就得知道时间/空…...
英语写作中“展示”、“表明”demonstrate、show、indicate、illustrate的用法
一、demonstrate、show、indicate在论文写作中主要用法是:demonstrate/show/indicate 从句: Sb./Sth. demonstrates/shows/indicates that ……从句中一般表达事实、观点和结论等。 例句: The authors demonstrated/showed/indicated that…...
Redis的java客户端
在Redis官网中提供了各种语言的客户端,地址:https://redis.io/resources/clients/ redis的java客户端 https://redis.io/resources/clients/#java 1.jedis使用 引入依赖 <dependency><groupId>redis.clients</groupId><artifac…...
Android环境配置笔记
文章目录 一、各环境文档二、参考 一、各环境文档 Gradle官方的兼容性文档:Java Compatibility 更新日期:2023.9.12 Android Gradle插件版本:Android Gradle Plugin 二、参考 参考文章:Android问题记录...
element-table 行的拖拽更改顺序(无需下载sortableJs
样例展示:vueelement 通过阅读element文档我们发现element并不提供拖拽相关的api 本博客通过element提供的行类名 注册函数 实现行与行的拖拽 1.设置el-table 的行样式类名 这里是用的是 function <el-table:data"outputData":row-class-name&qu…...
Docker部署jenkins
目录 一、jenkins原理二、Docker部署jenkins1.下载jenkins镜像文件2.查看下载的jenkins镜像3.创建Jenkins挂载目录并授权权限4.创建并启动Jenkins容器5.查看jenkins是否启动成功6.查看docker容器日志7.配置镜像加速8.访问Jenkins页面,输入ip地址加上9000端口9.获取管…...
从0到1学会Git(第三部分):Git的远程仓库链接与操作
写在前面:前面两篇文章我们已经学会了git如何在本地进行使用,这篇文章将讲解如何将本地的git仓库和云端的远程仓库链接起来并使用 为什么要使用远程仓库:因为我们需要拷贝我们的代码给别人以及进行协同开发,就需要有一个云端仓库进行代码的存储和同步&a…...
虚拟机Ubuntu操作系统常用终端命令(1)(详细解释+详细演示)
虚拟机Ubuntu操作系统常用终端命令 本篇讲述了Ubuntu操作系统常用的三个功能,即归档,软链接和用户管理方面的相关知识。希望能够得到大家的支持。 文章目录 虚拟机Ubuntu操作系统常用终端命令二、使用步骤1.归档1.1创建档案包1.2还原档案包1.3归档并压缩…...
redis实战-redis实现异步秒杀优化
秒杀优化-异步秒杀思路 未优化的思路 当用户发起请求,此时会请求nginx,nginx会访问到tomcat,而tomcat中的程序,会进行串行操作,分成如下几个步骤 1、查询优惠卷 2、判断秒杀库存是否足够 3、查询订单 4、校验是否是一…...
Python爬虫-IP隐藏技术与代理爬取
前言 在进行爬虫程序开发和运行时,常常会遇到目标网站的反爬虫机制,最常见的就是IP封禁,这时需要使用IP隐藏技术和代理爬取。 一、IP隐藏技术 IP隐藏技术,即伪装IP地址,使得爬虫请求的IP地址不被目标网站识别为爬虫。…...
二刷力扣--链表
链表 链表类型: 单链表(可以访问后面的一个节点) 双链表(可以访问前后节点) 循环链表(最后一个节点指向首节点) 在Python中定义单链表节点: class ListNode:def __init__(self, v…...
返回值加const ,为了不拷贝得到成员的值,但被赋值的左值也要const
1. getA 函数返回值 什么都不加,也改不了c里面a的指针指向 why?返回成员变量时,会复制一下。 返回成员变量时,一般会赋值一下没有RVO_地摊书贩的博客-CSDN博客 2. getA 函数返回值 加了引用, 就没有复制 3. getA 函数…...
本地如何使用HTTPS进行调试
在现代前端开发中,HTTPS已经成为不可或缺的一部分,因为它在保护用户数据和确保网站安全性方面发挥着关键作用。然而,有时在本地开发过程中启用HTTPS可能会变得有些复杂。在本文中,我们将介绍如何轻松地在本地进行HTTPS调试&#x…...
观察者模式:对象之间的订阅机制
欢迎来到设计模式系列的第十三篇文章!在之前的文章中,我们学习了许多常用的设计模式,今天我们将介绍观察者模式,它是一种行为型设计模式,用于定义对象之间的一对多依赖关系,当一个对象的状态发生变化时&…...
【1462. 课程表 IV】
来源:力扣(LeetCode) 描述: 你总共需要上 numCourses 门课,课程编号依次为 0 到 numCourses-1 。你会得到一个数组 prerequisite ,其中 prerequisites[i] [ai, bi] 表示如果你想选 bi 课程,你…...
Kerberos 身份验证
简介 Kerberos 是一种由 MIT(麻省理工大学)提出的一种基于加密 Ticket 的身份认证协议。它旨在通过使用密钥加密技术为客户端/服务器应用程序提供强身份验证,用于验证用户或主机的标识。。 适用范围:Windows Server 2022、Window…...
R语言贝叶斯METROPOLIS-HASTINGS GIBBS 吉布斯采样器估计变点指数分布分析泊松过程车站等待时间...
原文链接:http://tecdat.cn/?p26578 指数分布是泊松过程中事件之间时间的概率分布,因此它用于预测到下一个事件的等待时间,例如,您需要在公共汽车站等待的时间,直到下一班车到了(点击文末“阅读原文”获取…...
通付盾入选2023年度“上市苗圃工程”重点企业
近日,2023年度苏州工业园区企业上市苗圃工程认定名单公示,江苏通付盾科技有限公司成功入选园区“上市苗圃工程”重点企业。 2023年第一批次苗圃企业认定结果: 企业上市苗圃工程 上市企业是衡量地方综合经济实力的重要标尺,也是区…...
SpringMVC之文件上传下载
SpringMVC是一个基于Java的Web框架,它提供了一套用于构建Web应用程序的开发模型。在SpringMVC中,文件上传和下载是常见的功能之一。 SpringMVC文件上传和下载的介绍: 介绍文件上传: 在SpringMVC中,文件上传功能可以通…...
嵌入式IDE(2):KEIL中SCF分散加载链接文件详解和实例分析
在上一篇文章IAR中ICF链接文件详解和实例分析中,我通过I.MX RT1170的SDK中的内存映射关系,分析了IAR中的ICF链接文件的语法。对于MCU编程所使用的IDE来说,IAR和Keil用得比较多,所以这一篇文章就来分析一下Keil的分散文件.scf(scat…...
Linux防火墙常用操作及端口开放
Linux防火墙常用操作及端口开放 1.查看防火墙状态 firewall-cmd --state 2.开启防火墙 systemctl start firewalld.service 3.开启指定端口 firewall-cmd --zonepublic --add-port3306/tcp --permanent firewall-cmd --zonepublic --add-port6379/tcp --permanent 显示success表…...
湛江网站关键词优化/seo是如何做优化的
目录链接: 力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目: https://github.com/September26/java-algorithms 原题链接:力扣 描述: 给你一个下标从 0 开始、严格递增 的整数数组 nums 和一个正整数 diff 。如果满…...
墨刀做网站/近期网络舆情事件热点分析
jQuery(三) javascript跨域问题(JSONP解决)参考文章: (1)jQuery(三) javascript跨域问题(JSONP解决) (2)https://www.cnblogs.com/whgk/p/7102625.html 备忘一下。...
企业网站seo数据/营销型网站分为哪几种
2019独角兽企业重金招聘Python工程师标准>>> 邹建锋:手机游戏系列化运营模式探讨 国内移动市场在爆发式的增长,移动终端在大规模的普及,用户越来越习惯在手机上玩游戏,那么什么样的游戏才能赚钱?该文档…...
张家港高端网站建设公司/临安网站seo
轻量级网络之GhostNet前言动机Ghost模块G-bneckGhostNet网络结构实验性能消融实验Ghost模块 pytorch代码欢迎交流,禁止转载!!前言 《GhostNet: More Features from Cheap Operations》 论文地址:GhostNet: More Features from Ch…...
电子商务网站功能需求/磁力屋 最好用
1:Mongostat MongoDB2.6版本 MongoDB3.0版本 2:db.setProfilingLevel(2):打开profiler 类似于MySQL的slow log Profiler默认是关闭的,你可以选择全部开启,或者有慢查询的时候开启。 db.setProfilingLevel(level,<slowms>) 0…...
网站建设税费/sem推广代运营
索引类型 phoenix的索引大致分为两类global index和local index,好像和星环有点类似,其实这是hbase二级索引解决方案里面广为人知的两种方案,侧重点不同,使用场景也不一样。 global index,global是默认的索引格式。官…...