一、二叉搜索樹(shù)中兩節(jié)點(diǎn)的最小公共祖先：

??? 最初級(jí)的題目，在一顆二叉搜索樹(shù)中尋找兩節(jié)點(diǎn)的最小公共祖先。根據(jù)二叉搜索樹(shù)的特征，從根節(jié)點(diǎn)開(kāi)始查找，若兩節(jié)點(diǎn)的val值都小于當(dāng)前節(jié)點(diǎn)，則他們的最小公共祖先就去左子樹(shù)找，若兩節(jié)點(diǎn)的val值都大于當(dāng)前節(jié)點(diǎn)，則他們的最小公共祖先就去右子樹(shù)找。直到一個(gè)節(jié)點(diǎn)的值小于當(dāng)前節(jié)點(diǎn)，另一個(gè)節(jié)點(diǎn)的值大于當(dāng)前節(jié)點(diǎn)，那么當(dāng)前節(jié)點(diǎn)為最小公共祖先，即為找到了可以返回了。

c++代碼：

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root == NULL)return root;if (p->val<root->val && q->val<root->val)return lowestCommonAncestor(root->left, p, q);else if(p->val>root->val && q->val>root->val)return lowestCommonAncestor(root->right, p, q);return root; }

?

二、二叉樹(shù)中兩節(jié)點(diǎn)的最小公共祖先：

??? 1、二叉樹(shù)有指向父節(jié)點(diǎn)的指針：當(dāng)二叉樹(shù)中有指向父節(jié)點(diǎn)的指針時(shí)，可以倒過(guò)來(lái)看待這個(gè)問(wèn)題，即為求兩個(gè)鏈表的公共節(jié)點(diǎn)。從當(dāng)前節(jié)點(diǎn)開(kāi)始往根節(jié)點(diǎn)數(shù)，記錄總共有多少個(gè)節(jié)點(diǎn)，記下數(shù)字。然后大數(shù)字的鏈表上先走幾步到數(shù)字一樣，再兩節(jié)點(diǎn)都一起往根節(jié)點(diǎn)走，第一個(gè)相同的節(jié)點(diǎn)即為最小公共子節(jié)點(diǎn)。參見(jiàn)求鏈表相交的部分

?? 2、二叉樹(shù)沒(méi)有指向父節(jié)點(diǎn)的指針：

??? 這是普通的二叉樹(shù)中求兩節(jié)點(diǎn)的最小公共祖先。

思路一：二叉樹(shù)中兩節(jié)點(diǎn)無(wú)外乎這樣幾種情況，兩節(jié)點(diǎn)p和q相等；p是q的子樹(shù)或子樹(shù)中的節(jié)點(diǎn)；q是p的子樹(shù)或子樹(shù)中的節(jié)點(diǎn)；q和p是兩支子樹(shù)，這時(shí)候可以遞歸找到他們的父節(jié)點(diǎn)繼續(xù)前面的思路；

C++代碼如下：

bool ischild(TreeNode *pa, TreeNode *ch){if (ch == pa || pa==nullptr)return false;if (pa->left==ch || pa->right==ch)return true;return ischild(pa->left, ch)||ischild(pa->right, ch);}TreeNode* find_pa(TreeNode* root, TreeNode*cur){if (root->left == cur || root->right==cur)return root;if (ischild(root->left, cur))return find_pa(root->left, cur);elsereturn find_pa(root->right, cur);}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (p==q)return q;if (ischild(p, q))return p;if (ischild(q,p))return q;TreeNode *p_pa=find_pa(root, p);TreeNode *q_pa=find_pa(root, q);if (ischild(p_pa, q_pa) || p_pa==q_pa)return p_pa;else if(ischild(q_pa, p_pa))return q_pa;elsereturn lowestCommonAncestor(root, p_pa, q_pa);}

?

思路二：簡(jiǎn)單直接一點(diǎn)。當(dāng)root非空時(shí)，不斷從其左右子數(shù)搜索，①如果兩節(jié)點(diǎn)都在其左子樹(shù)，對(duì)其左子樹(shù)節(jié)點(diǎn)遞歸搜索；②如果兩節(jié)點(diǎn)都在其右子樹(shù)，對(duì)其右子樹(shù)節(jié)點(diǎn)遞歸搜索；③如果一個(gè)節(jié)點(diǎn)在左子樹(shù)一個(gè)節(jié)點(diǎn)在右子樹(shù)，則當(dāng)前節(jié)點(diǎn)即為最小公共祖先。

C++代碼如下：

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (root==NULL || root == p|| root==q)return root;if(p == q)return p;TreeNode* left = lowestCommonAncestor(root->left, p, q);TreeNode* right = lowestCommonAncestor(root->right,p,q);if (left!=NULL && right!=NULL)return root;else if(left == NULL)return right;return left;}

?

三、普通樹(shù)中兩節(jié)點(diǎn)的最小公共祖先：

??? 1、樹(shù)有指向父節(jié)點(diǎn)的指針：這種情況等同求鏈表的公共節(jié)點(diǎn)。同上參見(jiàn)求鏈表相交的部分

??? 2、樹(shù)沒(méi)有指向父節(jié)點(diǎn)的指針：此種情況我覺(jué)得可以參見(jiàn)上述第二種普通二叉樹(shù)求最小公共祖先（LCA）的方法，只是每次要在當(dāng)前節(jié)點(diǎn)的每一個(gè)子樹(shù)搜索。然而現(xiàn)在記錄另外一種方法,參加劍指offer50題：可以用兩個(gè)輔助空間，在當(dāng)前數(shù)中搜索兩個(gè)節(jié)點(diǎn)的路經(jīng)并存下來(lái)。然后從根節(jié)點(diǎn)開(kāi)始依次往后比較，記錄下最后一個(gè)相等的節(jié)點(diǎn)即為最小公共祖先。

C++代碼：

尋找路經(jīng)：

bool GetNodePath(TreeNode *pRoot, TreeNode *pNode, list<TreeNode*>&path){if (pRoot==pNode)return true;path.push_back(pRoot);bool found=false;vector<TreeNode*>::iterator i=pRoot->m_vChildren.begin();while(!found && i!=pRoot->m_vChildren.end()){　　found = GetNodePath(*i, pNode, path); ++i}if(!found)path.pop_back();return found;}

?

在兩個(gè)路經(jīng)中尋找最后的公共節(jié)點(diǎn)：

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)//按照值在尋找，而非節(jié)點(diǎn)。。其實(shí)也是可以按照節(jié)點(diǎn)來(lái)尋找的pLast = *iterator1;　　//這里按照我的理解 也應(yīng)該直接賦值 沒(méi)有解引用 因?yàn)榈鞅旧砭褪且粋€(gè)指針啊++iterator1;++iterator2;}return pLast;}

?

尋找最小公共祖先：

TreeNode *GetLastCommonParent(TreeNode* pRoot, TreeNode* pNode1, TreeNode* pNode2){if(pRoot==NULL || pRoot==pNode1 || pRoot==pNode2)　return pRoot;if (pNode1 == pNode2) return pNode1;List<TreeNode*>path1, path2;GetNodePath(pRoot,pNode1,path1);GetNodePath(pRoot,pNode2,path2);return GetLastCommonNode(path1,path2);}

?

轉(zhuǎn)載于:https://www.cnblogs.com/weiyi-mgh/p/6612146.html

總結(jié)

以上是生活随笔為你收集整理的两节点的最小公共祖先LCA的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。