二叉树：最近的公共祖先 Lowest Common Ancestor of a Binary Tree
已知二叉树，求二叉树中给定的两个节点的最近公共祖先。 最近公共祖先: 两节点v与w的最近公共祖先u，满足在树上最低(离根最 远)，且v,w两个节点都是u的子孙。
如上二叉树，6和8号节点的公共祖先有4，1；但是最近的公共祖先仅为4
这里我们发现，想要快速获取两个节点的最近的公共祖先节点，首先需要知道两个节点各自从根节点到当前的路径，即：
6号节点的路径为：[1,4,6]
8号节点的路径为：[1,4,5,8]
实现如下：
/*先序遍历查找路径*/
void getPathToNode(Tree *root, Tree *search, //root根节点，search为当前节点std::vector<Tree *> &path, //存储临时路径std::vector<Tree *> &result, //存储最终结果int &finish) { //是否找到的状态if (!root || finish ) { //如果找到或者根节点为空，则返回空return;}path.push_back(root); if (root == search) { //发现当前节点为我们要找的路径finish = 1;result = path; //将路径列表给予最终的结果}/*继续后序左右子树的查找*/getPathToNode(root -> left, search, path, result, finish);getPathToNode(root -> right, search, path, result, finish);/*发现没有找到，则将当前节点pop*/result.pop_back();
}
当我们能够知道两个节点的路径，那么接下来的祖先节点就非常好找了，实现如下：
Tree *getPublicNode(Tree *root, Tree *p, Tree *q) {if (root == NULL) {return NULL;}std::vector<Tree *> p_path;//p的最终路径std::vector<Tree *> q_path;//q节点的最终路径std::vector<Tree *> path;//存储临时路径int finish = 0;getPathToNode(root, p, path, p_path,finish);path.clear();finish = 0;getPathToNode(root, q, path, q_path,finish);int path_len = 0;if (p_path.size() > q_path.size()) { //需要取一个最短的路径进行后序的遍历path_len = q_path.size();}else {path_len = p_path.size();}Tree *result;for (int i = 0;i < path_len; ++i) { //从开始（根节点）遍历到叶子节点，越靠后的节点越为最近的公共祖先节点if (p_path[i] == q_path[i]) {result = p_path[i];}}return result;
}
相关文章：
VS不显示最近打开的项目
VS2012不显示最近打开的项目 解决方法， 在"运行"中输入 " gpedit.msc"打开后在"用户配置"-"管理模板"-"任务栏和开始菜单" 然后将用户配置-->管理模板-->不保留最近打开文档的历史 将此选项设置为禁用 源…
河科大c语言上机实验答案,2016年河南科技学院信息工程学院C语言上机编程考研复试题库...
一、选择题1． 以下选项中，能用作数据常量的是( )。答:D【解析】A 项错误，十六进制数用数学0和字符x (或大写字母X )开头；B 项错误，八进制整数常量以数字0开始，有效数字为0〜7; C项错误，C 语言中…
无符号数溢出之后
2019独角兽企业重金招聘Python工程师标准>>> [rootcentos ~]# cat test.c #include <stdio.h>int main() {unsigned short i 0x0;while(1){printf("%u \n",i);if(i 0) //溢出之后 又会回到 0 所以不会 死循环break;} } 转载于:https://my.oschin…
加载BeanFactory
前言 上一篇文章讲述了ApplicationContext扩展功能的之一：环境准备。这篇文章接着讲述ApplicationContext的扩展功能-----加载BeanFactory，也就是初始化BeanFactory，并进行XML文件的读取。 加载BeanFactory obtainFreshBeanFactory方法从字面…
t-top 命令详解
前言 展示操作系统进程信息。动态得，实时得展示正在运行的操作系统进程信息。 所显示的系统摘要信息的类型以及为进程显示的信息的类型，顺序和大小都是用户可配置的，并且可以使配置在重新启动后保持不变。该程序为流程操作提供了一个有限的交…
怎么看懂c语言程序,求讲解一下这个程序，我看了1个小时都没有看懂，
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼# include #define N 9void fun(int a[], int n){ int i,j, max, min, px, pn, t;for (i0; i{/**********found**********/max min ___a[i]__;px pn i;for (ji1; j/**********found**********/if (max<___a>{ max a[j];…
【转】Winform输入法控制
来源：http://blog.itpub.net/23109131/viewspace-630576 想实现输入法切换：思路，找出当前系统所有输入法总个数，当前输入法在总输入法中的索引，通过改变索引值，来切换输入法 void input() {//变全角为半角的…
vector与结构体联合使用 在磁盘中生成.txt 文件
一下纯属个人总结、欢迎拍砖！谢谢 我意思到以练促进学习C编程基础是很有帮助的 这篇文章是我为了熟悉掌握文件流和STL中的vector以及结构体三个只知识点所写的代码： #include <string> #include <stdlib.h> #include <iostream> #incl…
SQL Server 2008 R2如何开启数据库的远程连接
SQL Server 2008 R2如何开启数据库的远程连接 转载于:https://www.cnblogs.com/macT/p/10213025.html
二分法：二分查找（递归+非递归）实现
二分查找又称折半查找，首先，假设表中元素是按升序排列，将 表中间位置的关键字与查找关键字比较: 如果两者相等，则查找成功;否则利用中间位置将表分成前、后两个子表: 1)如果中间位置的关键字大于查找关键字，则进一步查…
mongodb数据库的一些常用命令列表
超级用户相关：use admin#增加或修改用户密码db.addUser(ixigua,pwd)#查看用户列表db.system.users.find()#用户认证db.auth(ixigua,pwd)#删除用户db.removeUser(mongodb)#查看所有用户show users#查看所有数据库show dbs#查看所有的collectionshow collections#查看…
c语言函数库哪里keyk,[精品]C语言库函数(字母G-K)-教案.doc
[精品]C语言库函数(字母G-K)-教案C语言库函数(字母G-K)- -??????????????????????????????????????(G类字母) - 1函数名: gcvt 功 能: 把浮点数转换成字符串 用 法: char *gcvt(double value, int ndigit, char *buf); 程序例: #include…
超链接调用js函数
<a href"javascript:gouwu()" ><span class"Buy" id"buyButton"></span></a>超链接调用js前面要加javascript:****************************SuppressWarningsJ2SE 提供的最后一个批注是 SuppressWarnings。该批注的作用…
iOS 轻击、触摸和手势的检测
一、检测捏合手势( UIPinchGestureRecognizer): //设定一个实例变量存储手指之间的其起始距离 property (assign, nonatomic) CGFloat initialFontSize;//调用：UIPinchGestureRecognizer *pinch [[UIPinchGestureRecognizeralloc]initWithTarget:selfaction:select…
二分法：search insert position 插入位置
问题描述： 给定一个排序数组nums(无重复元素)与目标值target，如果target在nums里 出现，则返回target所在下标，如果target在nums里未出现，则返回target应该 插入位置的数组下标，使得将target插入数组nums后&…
c语言课程设计学生籍贯信息记录簿,C语言课程设计 学生籍贯信息记录簿设计.doc...
C语言与程序设计课程设计学生籍贯信息记录簿设计学 院 信息工程班 级 物联1301班学 号 131408119姓 名 滕玲一．设计目的该软件主要是编辑一个学生籍贯信息记录簿记录每个学生信息，包括：学号、姓名、籍贯。具体功能：1.创建信息链表…
SharePoint使用BCS开发你第一个应用程序（三）
SharePoint使用BCS开发你第一个应用程序（三） 创建外部内容类型。 创建外部内容类型有三种不同方式：1. 在记事本上手写XML代码（不推荐）。2. 使用SharePoint Designer 2010 创建（推荐）。3. 使用VS…
Java Coverage(Cobertura)工具
首先是下载Cobertura的jar包了，这个工具底层是JCoverage，熟悉Jcoverage的对这个也不会陌生的。 Cobertura官网 http://cobertura.sourceforge.net/ 大家可以了解很多东西，比如现在的作者啊什么，这里就不介绍了 然后点Download&…
Java 内部类及其原理
Java中实现内部类 内部类相信大家都用过很多次了，就不说它是怎么用的了。 内部类 1.成员内部类 需要注意的是， 当成员内部类拥有和外部类同名的成员变量或这方法时， 默认情况下访问的是内部类的成员， 如要访问外部类的同名成员&am…
二分法：查找区间search for a range
问题描述： 给定一个排序数组nums(nums中有重复元素)与目标值target，如果 target在nums里出现，则返回target所在区间的左右端点下标，[左端点, 右端点]，如果target在nums里未出现，则返回[-1, -1]。 例如: ar…
c语言向表格内存入数据,怎么实现横向到存入多个单元格,在列数固定的报表中逐格横向填充数据并折行...
在很多需要打印的报表中，受限于纸张的大小，往往会限制行数或者固定列数。我们在《单据类报表的制作》一文中，曾经介绍了限制了行数的情况如何实现，现在，我们再来看一下，在固定了列数的情况下，如…
设计模式之简单工厂模式
一、概述 工厂模式具体包括了简单工厂、工厂方法、抽象工厂，它们是按照从简单到复杂的顺序排列的，属于设计模式中的创建型，其中简单工厂并不属于GOF的23中模式。 但是它是理解其它的工厂模式的一个很好的基础，所以很多人在讲述设…
zendserver的版本是怎么回事？免费版哪里去了？
zend server 的版本，官网上说是四个版本，免费版、小企业版、专业版、企业版。 但下载只有一个版本。在下载的页面中大大的free download 很是显眼。安装完成之后显示为企业版。使用几天之后，显示你的许可即将到期。 输入密码，登录…
sql-case when 条件1 then 取值1 when 条件2 then 取值2 else 取值3 end
遇到 XXX情况 就 XXX 遇不到就 XXX 结束case when …… then …… else …… end 例如一个3条件取值的字段： case when 条件1 then 取值1 when 条件2 then 取值2 else 取值3 end when后接条件语句，then后为字段取值（数值或字符串等都可以&…
二叉树：二叉搜索树的创建和插入
二叉搜索树又名二叉排序树。 大概简略的思维导图如下，方便记忆特性 基本二叉搜索树创建过程如下 /*数据结构如下*/ typedef struct tree {int data;struct tree *left NULL;struct tree *right NULL; }Tree,*TreeNode;/*Node 为二叉树根节点，insert…
ie7和ie8 select使用jquery clone不兼容处理
本文解决方案基于http://blog.csdn.net/zzx3q/article/details/8017794 在ie7和ie8下，用jquery clone复制一个select，复制的select是本体的select初始化时的一个副本，无法复制目前本体select选择。 解决方案： <!DOCTYPE html&g…
c语言中floox的头文件,PC-1211袖珍计算机在合成氨厂生产中的应用 第五讲 循环语句(FOR-NEXT语句)...
PC-1211袖珍计算机在合成氨厂生产中的应用 第五讲 循环语句(FOR-NEXT语句)在化工生产中为了分析两个或两个以上参数对生产的影响往往需要进行某些有规律的重复计算。这些计算在程序中可以用赋值语句或条件语句来实现,但从下面的介绍可以看出,这时若采用循(本文共7页)阅读全文&g…
C#Winform+WindowsAPI做个剪贴板无缝自动保存器（视频截图利器）
C#WinformWindowsAPI做个剪贴板无缝自动保存器（视频截图利器） (本文最新代码已上传到GitHub，地址在（https://github.com/bitzhuwei/ClipboardImageSaver）) 利用C#和Window API做了个自动保存剪贴板内的图片的工具&…
Kafka配置SASL/PLAIN认证
1、安装zk，kafka 2、配置server.properties security.inter.broker.protocolSASL_PLAINTEXT sasl.mechanism.inter.broker.protocolPLAIN sasl.enabled.mechanismsPLAIN listenersSASL_PLAINTEXT://0.0.0.0:9092 advertised.listenersSASL_PLAINTEXT://host:9092 3…
二叉树：二叉搜索树的编码和解码
二叉搜索树的编码和解码描述： 编码：即将一个二叉搜索树编码，节点数值转换为字符串 解码：即将一个字符串解码，数值转换为对应的二叉搜索树的节点 过程导图如下： 针对性编码实现如下: /*数字转字符串*/ vo…