首页 技术 正文
技术 2022年11月23日
0 收藏 930 点赞 2,158 浏览 1479 个字

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______3______
/ \
___5__ ___1__
/ \ / \
6 _2 0 8
/ \
7 4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

思路:

  通过先序遍历,分别找到要查找结点(5 , 4)的路径(3->5 , 3->5->2->4),然后求路径序列中最后一个公共结点(5)即为所求。

C++:

 /**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
private:
vector<TreeNode* > plist; public:
void rec(TreeNode *root, TreeNode *tar, vector<TreeNode* >& res)
{
if(root == tar)
{
vector<TreeNode* >::iterator it = plist.begin();
for(; it != plist.end(); it++)
res.push_back(*it); return ;
} if(root->left != )
{
plist.push_back(root->left);
rec(root->left, tar, res);
plist.pop_back();
} if(root->right != )
{
plist.push_back(root->right);
rec(root->right, tar, res);
plist.pop_back();
}
} TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root == )
return ; vector<TreeNode* > list1, list2; plist.push_back(root);
rec(root, p, list1); plist.clear();
plist.push_back(root);
rec(root, q, list2); TreeNode *ret = ;
vector<TreeNode* >::iterator it1 = list1.begin();
vector<TreeNode* >::iterator it2 = list2.begin();
for(; it1 != list1.end() && it2 != list2.end(); it1++, it2++)
{
if(*it1 == *it2)
ret = *it1;
} return ret;
}
};
相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:878 阅读:9,088
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:807 阅读:5,565
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:569 阅读:6,413
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:733 阅读:6,186
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:7,822
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:4,905