生活随笔
收集整理的這篇文章主要介紹了
程序员面试100题之十六：二叉树中两个节点的最近公共父节点（最低的二叉树共同祖先）
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
這個問題可以分為三種情況來考慮：
情況一：root未知，但是每個節(jié)點都有parent指針
此時可以分別從兩個節(jié)點開始，沿著parent指針走向根節(jié)點，得到兩個鏈表，然后求兩個鏈表的第一個公共節(jié)點，這個方法很簡單，不需要詳細(xì)解釋的。
情況二：節(jié)點只有左、右指針，沒有parent指針，root已知
思路：有兩種情況，一是要找的這兩個節(jié)點（a, b），在要遍歷的節(jié)點（root）的兩側(cè)，那么這個節(jié)點就是這兩個節(jié)點的最近公共父節(jié)點；
二是兩個節(jié)點在同一側(cè)，則 root->left 或者 root->right 為 NULL，另一邊返回a或者b。那么另一邊返回的就是他們的最小公共父節(jié)點。
遞歸有兩個出口，一是沒有找到a或者b，則返回NULL；二是只要碰到a或者b，就立刻返回。
typedef struct BiTNode { char data; struct BiTNode lchild, rchild; }BinaryTreeNode; BinaryTreeNode findLowestCommonAncestor(BinaryTreeNode root , BinaryTreeNode* a , BinaryTreeNode* b){ if(root == NULL) return NULL; if(root == a || root == b) return root;BinaryTreeNode* left = findLowestCommonAncestor(root->lchild , a , b);BinaryTreeNode* right = findLowestCommonAncestor(root->rchild , a , b); if(left && right) return root; return left ? left : right;}
情況三： 二叉樹是個二叉查找樹，且root和兩個節(jié)點的值(a, b)已知
BinaryTreeNode* findLowestCommonAncestor(BinaryTreeNode* root , BinaryTreeNode* a , BinaryTreeNode* b){ char min , max; if(a->data < b->data)min = a->data , max = b->data; elsemin = b->data , max = a->data; while(root){ if(root->data >= min && root->data <= max) return root; else if(root->data < min && root->data < max)root = root->rchild; elseroot = root->lchild;} return NULL;}
1、二叉樹定義：
typedef struct BTreeNodeElement_t_ { void *data;} BTreeNodeElement_t; typedef struct BTreeNode_t_ {BTreeNodeElement_t *m_pElemt; struct BTreeNode_t_ *m_pLeft; struct BTreeNode_t_ *m_pRight;} BTreeNode_t;
2、查找二叉樹中兩個節(jié)點的最低祖先節(jié)點（或最近公共父節(jié)點等）
? ? 最低祖先節(jié)點就是從根節(jié)點遍歷到給定節(jié)點時的最后一個相同節(jié)點
例如：
? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ? ? ??? ??A
? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??B? ??? ??? ??? ??? ??? ? ? ??? ??? ??? ??? ??C
? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ? D? ??? ??? ??? ??? ??? ? E? ??? ??? ??? ??? ???F? ??? ??? ??? ??? ??? ??? ??? ? G
? ??? ??? ??? ??? ??? ??? ??? ??? ? H? ??? ??? ? I? ??? ??? ? J? ??? ??? ? K? ??? ? L? ??? ? M? ??? ??? ??? ??? ??? ? N? ? O
如上圖，H和J的最低祖先節(jié)點是B。
因為從根節(jié)點A到H的鏈路為： ? A ? ? B ? ?D ? H
從根節(jié)點A到J的鏈路為： ? A ? B ? ?E ? J
查看鏈路節(jié)點可知，B是最后一個相同節(jié)點，也就是所謂的最近公共父節(jié)點或者說最低祖先節(jié)點。
（1）遞歸方式
如果給定pRoot是NULL，即空樹，則返回的公共節(jié)點自然就是NULL；
如果給定pRoot與兩個節(jié)點中任何一個相同，說明，pRoot在就是所要找的兩個節(jié)點之一，則直接返回pRoot，表明在當(dāng)前鏈路中找到至少一個節(jié)點；
如果給定pRoot不是兩個節(jié)點中任何一個，則說明，需要在pRoot的左右子樹中重新查找，此時有三種情況：兩個節(jié)點都在左子樹上；兩個節(jié)點都在右子樹上；一個在左子樹，一個在右子樹上；具體來說，就是：
? ??? ? 情況一：如果左子樹查找出的公共節(jié)點是NULL，則表明從左子樹根節(jié)點開始到左子樹的所有葉子節(jié)點等所有節(jié)點中，沒有找到兩個節(jié)點中的任何一個，這就說明，這兩個節(jié)點不在左子樹上，不在左子樹，則必定在右子樹上；
? ??? ?情況二：如果右子樹查找的公共節(jié)點是NULL，說明在右子樹中無法找到任何一個節(jié)點，則兩個節(jié)點必定在左子樹上；
? ? ? ?情況三： 如果左右子樹查找的公共節(jié)點都不是NULL，說明左右子樹中各包含一個節(jié)點，則當(dāng)前節(jié)點pRoot就是最低公共節(jié)點，返回就可以了。
? ? ? ?三種情況是互斥的， 只能是其中之一。
BTreeNode_t *GetLastCommonParent( BTreeNode_t *pRoot, BTreeNode_t *pNode1, BTreeNode_t *pNode2){ if( pRoot == NULL ) return NULL; if( pRoot == pNode1 || pRoot == pNode2 ) return pRoot; BTreeNode_t *pLeft = GetLastCommonParent( pRoot->m_pLeft, pNode1, pNode2); BTreeNode_t *pRight = GetLastCommonParent( pRoot->m_pRight, pNode1, pNode2); if( pLeft == NULL ) return pRight; if ( pRight == NULL ) return pLeft; return pRoot;}
（2）非遞歸方式：
BTreeNode_t *GetLastCommonParent（BTreeNode_t *pRoot, BTreeNode_t *pNode1, BTreeNode_t *pNode2){ if( pRoot == NULL || pNode1 == NULL || pNode2 == NULL) return NULL; vector < BTreeNode_t *> vec1; vector <BTreeNode_t *> vec2; stack <BTreeNode_t *> st; bool findflag1 = false; bool findflag2 = false;BTreeNode_t *commonParent = NULL; while( pRoot != NULL || !st.empty() ){ while( pRoot != NULL ){ if( findflag1 == false){vec1.push_back( pRoot); if( pRoot == pNode1)findflag1 = true;} if( findflag2 == false ){vec1.push_back( pRoot); if( pRoot == pNode2 )findflag2 = true;} if( findflag1 == true && findflag2 == true) break; st.push( pRoot);pRoot = pRoot->m_pLeft;} while( !st.empty()){pRoot = st.top();st.pop();pRoot = pRoot->right; if( findflag1 == false )vec1.pop_back(); if( findflag2 == false )vec2.pop_back();} if( findflag1 == true && findflag2 == true) break; } if( findflag1 == true && findflag2 == true){ vector< BTreeNode_t *> ::iterator iter1 = vec1.begin(); vector< BTreeNode_t *> ::iterator iter2 = vec2.begin(); while( iter1 != vec1.end() && iter2 != vec2.end() ){ if( *iter1 == *iter2) commonParent = *iter1; else break; ++iter1; ++iter2;} } vec1.clear(); vec2.clear(); st.clear(); return commonParent;}
</pre><pre>
總結(jié)
以上是生活随笔為你收集整理的程序员面试100题之十六：二叉树中两个节点的最近公共父节点（最低的二叉树共同祖先）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
