二叉樹兩個結點的最低共同父結點 微信：318175542
來源：程序員人生 發布時間：2015-05-15 08:29:28 閱讀次數：2953次
入2叉樹中的兩個結點，輸出這兩個結點在數中最低的共同父結點。
分析：求數中兩個結點的最低共同結點是
面試中常常出現的1個問題。這個問題至
少有兩個變種。
第1變種是2叉樹是1種特殊的2叉樹：查找2叉樹。也就是樹是排序過的，位于
左子樹上的結點都比父結點小， 而位于右子樹的結點都比父結點大。 我們只需要從根結點開
始和兩個結點進行比較。 如果當前結點的值比兩個結點都大， 則最低的共同父結點1定在當
前結點的左子樹中。 如果當前結點的值比兩個結點都小， 則最低的共同父結點1定在當前結
點的右子樹中。
第2個變種是樹不1定是2叉樹，每一個結點都有1個指針指向它的父結點。因而我
們可以從任何1個結點動身， 得到1個到達樹根結點的單向鏈表。 因此這個問題轉換為兩個
單向鏈表的第1個公共結點。
思路：現在我們回到這個問題本身。所謂共同的父結點，就是兩個結點都出現在這個結點
的子樹中。假設我們從頭部開始遍歷，1旦發現有節點和兩個節點中的1個相等，那末此節點就是目標節點，要末公共父節點在左子樹，要末在右子樹。如果發現兩個節點1個在左子樹，1個在右子樹，那末當前節點就是公共父節點，如果發現有都在右子樹，那末公共父節點就在右子樹，如果發現都在左子樹，那末公共父節點在右子樹
bool FindNode(BinTree* root,BinTree* node)
{
if(root == NULL)
return false;
if(root == node)
return true;
return (FindNode(root->left,node) ||FindNode(root->right,node));
}
BinTree* LCP(BinTree* root,BinTree* first,BinTree* second)
{
if(root == first || root == second)
return root;
bool isLeft = false;
isLeft = FindNode(root->left,first);
if(isLeft)
{
if(FindNode(root->left,second))
return LCP(root->left,first,second);
else
return root;
}
else
{
if(FindNode(root->right,second))
return LCP(root->right,first,second);
else
return root;
}
}
另外一種實現：
/*
求2叉樹中兩個節點的最低公共先人節點
*/
BinTree* LCA(BinTree* root,BinTree* first,BinTree* second)
{
if(root == first || root == second )
return root;
if(root == NULL)
return NULL;
BinTree* left = LCA(root->left,first,second);
BinTree* right = LCA(root->right,first,second);
if(left == NULL)
return right;
else if(right == NULL)
return left;
else
return root;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
