首页 > 代码库 > 寻找二叉树中的最低公共祖先结点----LCA(Lowest Common Ancestor )问题(递归)
寻找二叉树中的最低公共祖先结点----LCA(Lowest Common Ancestor )问题(递归)
转自 剑指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(1); TreeNode *p2 = new TreeNode(2); TreeNode *p3 = new TreeNode(3); TreeNode *p4 = new TreeNode(4); TreeNode *p5 = new TreeNode(5); TreeNode *p6 = new TreeNode(6); TreeNode *p7 = new TreeNode(7); TreeNode *p8 = new TreeNode(8); TreeNode *p9 = new TreeNode(9); TreeNode *p10 = new TreeNode(10); 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
寻找二叉树中的最低公共祖先结点----LCA(Lowest Common Ancestor )问题(递归)