二叉树：最近的公共祖先 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;
}
更多相关：
-
当一个IT组织开始走到需要实施网络边缘的旅程时，他们很快意识到面对的挑战与他们在传统数据中心内所经历的挑战不同。 第一个挑战是空间。与更大的核心或区域数据中心同类产品相比，许多边缘站点的物理尺寸更小，因此，需要仔细计划好，尝试在未为其专门设计的空间中安装硬件。 第二个挑战是运行环境。还必须解决的可能面对的冷热温度变化 ，天气，无...
-
单向循环链表单链表的一个变形是单向循环链表, 链表的最后一个节点的next域不再为None, 而是指向链表的头节点.单向循环链表如图所示:单向循环链表同样单向循环链表也是要使用python来对它的基本功能进行一个封装. 总体大致的功能如下:is_empty() 判断链表是否为空length() 返回链表的长度travel() 遍历ad...
-
题目： 二叉搜索树与双向链表 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。 为了让您更好地理解问题，以下面的二叉搜索树为例： 我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一...
-
题目：删除链表的节点 给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。 返回删除后的链表的头节点。 注意：此题对比原题有改动 示例 1: 输入: head = [4,5,1,9], val = 5 输出: [4,1,9] 解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为...
-
【从零开始的ROS四轴机械臂控制】（一）- 实际模型制作、Solidworks文件转urdf与rviz仿真 一、模型制作 1.实际模型制作 2.Solidworks模型制作 二、Solidworks文件转urdf 1.sw_urdf_exporter插件 2.添加坐标系和转轴 3.导出urdf文件 三、rivz仿真...
-
Open3D是一个开源库，支持快速开发和处理3D数据。Open3D在c++和Python中公开了一组精心选择的数据结构和算法。后端是高度优化的，并且是为并行化而设置的。本系列学习计划有Blue同学作为发起人，主要以Open3D官方网站的教程为主进行翻译与实践的学习计划。点云PCL公众号作为免费的3D视觉，点云交流社区，期待有使用Op...
-
业务场景： 我在一个bash脚本中修改了PATH变量的内容，并将其保存到/etc/profile文件中，同时执行了 source /etc/profile 但是当脚本退出时，我发现PATH变量还是没有修改生效，但是，如果我在命令行再直接执行 source /etc/profile 才发现PATH生效了。 请问，这是什么原因呢？...
-
给定一个二叉树与整数sum，找出所有从根节点到叶结点的路径，这些路 径上的节点值累加和为sum 即创建一个二叉树，要求二叉树中有一个路径从根节点到叶节点到路径加起来代表到和为 给定的sum 如下二叉树 给定路径之和为18，则需要输出两条路径： [1,4,5,8] [1,4,6,7] 同样，这个过程我们可以使用先序深度优先搜索，同...
-
export PATH=$PATH:/usr/local/php/bin 转载于:https://www.cnblogs.com/ttiandeng/p/6554902.html...
-
2019独角兽企业重金招聘Python工程师标准>>> 每台计算机安装程序不同，环境变量path会有不同，若误删了环境变量path,可以如下完美解决. Win+R 输入regedit打开注册表(开始-运行里输入regedit） 找到 HKEY_LOCAL_MACHINESYSTEMControlSet002...
-
L3-010. 是否完全二叉搜索树 时间限制 400 ms 内存限制 65536 kB 代码长度限制 8000 B 判题程序 Standard 作者 陈越 将一系列给定数字顺序插入一个初始为空的二叉搜索树（定义为左子树键值大，右子树键值小），你需要判断最后的树是否一棵完全二叉树，并且给出其层序遍历的结果。 输入格...
-
一个用于实现初始化指定个数的完全二叉树，以及两个非递归的深度优先遍历，和广度优先遍历 package fifth; import java.util.Random; public class Tool{ public static Random rand= new Random(); } --------------...