寻找二叉树中的最低公共祖先结点----LCA(Lowest Common Ancestor )问题(递归)
2024-10-19 06:27:35
转自 剑指Offer之 - 树中两个结点的最低公共祖先
题目:
求树中两个节点的最低公共祖先。
思路一:
——如果是二叉树,而且是二叉搜索树,那么是可以找到公共节点的。
二叉搜索树都是排序过的,位于左子树的节点都比父节点小,而位于右子树上面的节点都比父节点大。
如果当前节点的值比两个结点 的值都大,那么最低的共同的父节点一定是在当前节点的左子树中,于是下一步遍历当前节点的左子节点。
如果当前节点的值比两个结点的值都小,那么最低的共同的父节点一定是在当前节点的右子树中,于是下一步遍历当前节点的右子节点。
这样从上到下,找到的第一个在两个输入结点的值之间的节点,就是最低的公共祖先。
题目和代码参考:http://blog.csdn.net/u012243115/article/details/46875537。
思路二:
如果这棵树不是二叉搜索树,甚至连二叉树都不是,而只是普通的树。
——如果有指向父节点的指针,那么这个题目转换成了求,两个双向链表的第一个公共结点的问题。
思路三:
这棵树是普通的树,而且这个树中的结点没有指向父节点的指针。
——遍历这个树,看以这个节点为根的子树是否包含这两个节点,如果包含,判断这个节点的子节点是否包含,
——知道子节点都不包含而这个当前的节点包含,那么这个节点就是最低的公共祖先。
ps.这里存在大量的重复遍历,效率不高。
思路三:
这棵树是普通的树,而且这个树中的结点没有指向父节点的指针。
——用两个链表分别保存从根节点到输入的两个结点的路径,然后把问题转换成两个链表的最后公共节点。
代码:
(这里假设树是普通二叉树,用思路三求解)
#include <iostream>
#include <list>
using namespace std; struct TreeNode
{
int m_nValue;
TreeNode *m_pLeft;
TreeNode *m_pRight;
TreeNode(){}
TreeNode(int value):m_nValue(value),m_pLeft(NULL),m_pRight(NULL){}
}; //得到pNode结点的路径,放入path中 也可以用栈来实现 ,递归的本质就是一个压栈和出栈的过程
// 本题可为剑指offer原题P252,其解法可参考面试题25(P143)
bool GetNodePath(TreeNode * pRoot , TreeNode *pNode , list<TreeNode *> &path)
{
if(pRoot == NULL)
return false;
path.push_back(pRoot); bool found = false;
if(pRoot == pNode)
{
found = true;
return found;
}
// 注意理解这里的递归问题
found = GetNodePath(pRoot->m_pLeft , pNode , path) || GetNodePath(pRoot->m_pRight , pNode , path);
if(!found)
path.pop_back();
return found;
} //找到两条路径的最后一个公共结点即是公共祖先
TreeNode * GetLastCommonNode(const list<TreeNode *> &path1 , const list<TreeNode*> &path2)
{
list<TreeNode *>::const_iterator iterator1 = path1.begin();
list<TreeNode *>::const_iterator iterator2 = path2.begin();
TreeNode *pLast = NULL;
while(iterator1 != path1.end() && iterator2 != path2.end())
{
if(*iterator1 == *iterator2)
pLast = *iterator1;
iterator1++;
iterator2++;
}
return pLast;
} TreeNode * GetLastCommonNodeParent(TreeNode *pRoot , TreeNode *pNode1 , TreeNode *pNode2)
{
if(pRoot == NULL || pNode1 == NULL || pNode2 == NULL)
return NULL;
list<TreeNode *> path1;
GetNodePath(pRoot , pNode1 , path1);
list<TreeNode *> path2;
GetNodePath(pRoot , pNode2 , path2);
return GetLastCommonNode(path1 , path2);
} TreeNode * findLCA(TreeNode *pRoot , TreeNode *pNode1 , TreeNode *pNode2)
{
if(pRoot == NULL)
return NULL;
if(pRoot == pNode1 || pRoot == pNode2)
return pRoot;
TreeNode *left_lca = findLCA(pRoot->m_pLeft , pNode1 , pNode2);
TreeNode *right_lca = findLCA(pRoot->m_pRight , pNode1 , pNode2);
if(left_lca && right_lca )
return pRoot;
return (left_lca != NULL) ? left_lca : right_lca;
} int main()
{
TreeNode *p1 = new TreeNode();
TreeNode *p2 = new TreeNode();
TreeNode *p3 = new TreeNode();
TreeNode *p4 = new TreeNode();
TreeNode *p5 = new TreeNode();
TreeNode *p6 = new TreeNode();
TreeNode *p7 = new TreeNode();
TreeNode *p8 = new TreeNode();
TreeNode *p9 = new TreeNode();
TreeNode *p10 = new TreeNode();
p1->m_pLeft = p2;
p1->m_pRight = p3;
p2->m_pLeft = p4;
p2->m_pRight = p5;
p3->m_pLeft = p6;
p3->m_pRight = p7;
p4->m_pLeft = p8;
p4->m_pRight = p9;
p5->m_pLeft = p10;
TreeNode *p;
p = GetLastCommonNodeParent(p1 , p8 , p7);//p8和p7的最近公共祖先
if(p)
cout<<"最近的公共祖先是p"<<p->m_nValue<<endl;
else
cout<<"不存在公共祖先"<<endl;
TreeNode *q;
q = findLCA(p1 , p8 , p7);//p8和p7的最近公共祖先
if(q)
cout<<"最近的公共祖先是p"<<q->m_nValue<<endl;
else
cout<<"不存在公共祖先"<<endl;
}
findLCA参考:http://www.acmerblog.com/lca-lowest-common-ancestor-5574.html
最新文章
- C语言基础(2)-常量
- WebIM 聊天 Demo
- nginx实现动静分离
- 第二十一篇:SOUI中的控件注册机制
- uploadify 报错集锦
- PHP会话处理相关函数介绍
- Utopian Tree in Java
- IOS基础 Day-1手动内存管理
- C++(指针)
- UIKit控件直接显示网页文字内容
- Python面向对象编程(二)
- HDU2057 A + B Again
- Detours HOOK 库 过滤LoadLibraryExW
- linux查看主板型号、CPU、显卡、硬盘等信息
- Linux学习之RPM包管理-rpm命令管理(十六)
- cookie和session的关联关系
- JavaScript ES6格式化字符串方法
- OSLab文件描述符
- VS2013快速安装教程
- vsphere web client 使用中文的解决办法