快捷導(dǎo)航

深入二叉樹(shù)兩個(gè)結(jié)點(diǎn)的最低共同父結(jié)點(diǎn)的詳解

更新時(shí)間：2013年05月23日 18:21:23 作者：

本篇文章是對(duì)二叉樹(shù)兩個(gè)結(jié)點(diǎn)的最低共同父結(jié)點(diǎn)進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下

題目：二叉樹(shù)的結(jié)點(diǎn)定義如下：

struct TreeNode
   {
              int m_nvalue;
             TreeNode* m_pLeft;
             TreeNode* m_pRight;
};

輸入二叉樹(shù)中的兩個(gè)結(jié)點(diǎn)，輸出這兩個(gè)結(jié)點(diǎn)在數(shù)中最低的共同父結(jié)點(diǎn)。
分析：求數(shù)中兩個(gè)結(jié)點(diǎn)的最低共同結(jié)點(diǎn)是面試中經(jīng)常出現(xiàn)的一個(gè)問(wèn)題。這個(gè)問(wèn)題至少有兩個(gè)變種。
第一變種是二叉樹(shù)是一種特殊的二叉樹(shù)：查找二叉樹(shù)。也就是樹(shù)是排序過(guò)的，位于左子樹(shù)上的結(jié)點(diǎn)都比父結(jié)點(diǎn)小，而位于右子樹(shù)的結(jié)點(diǎn)都比父結(jié)點(diǎn)大。我們只需要從根結(jié)點(diǎn)開(kāi)始和兩個(gè)結(jié)點(diǎn)進(jìn)行比較。如果當(dāng)前結(jié)點(diǎn)的值比兩個(gè)結(jié)點(diǎn)都大，則最低的共同父結(jié)點(diǎn)一定在當(dāng)前結(jié)點(diǎn)的左子樹(shù)中。如果當(dāng)前結(jié)點(diǎn)的值比兩個(gè)結(jié)點(diǎn)都小，則最低的共同父結(jié)點(diǎn)一定在當(dāng)前結(jié)點(diǎn)的右子樹(shù)中。
第二個(gè)變種是樹(shù)不一定是二叉樹(shù)，每個(gè)結(jié)點(diǎn)都有一個(gè)指針指向它的父結(jié)點(diǎn)。于是我們可以從任何一個(gè)結(jié)點(diǎn)出發(fā)，得到一個(gè)到達(dá)樹(shù)根結(jié)點(diǎn)的單向鏈表。因此這個(gè)問(wèn)題轉(zhuǎn)換為求兩個(gè)單向鏈表的第一個(gè)公共結(jié)點(diǎn)。
現(xiàn)在我們回到這個(gè)問(wèn)題本身。所謂共同的父結(jié)點(diǎn)，就是兩個(gè)結(jié)點(diǎn)都出現(xiàn)在這個(gè)結(jié)點(diǎn)的子樹(shù)中。因此我們可以定義一函數(shù)，來(lái)判斷一個(gè)結(jié)點(diǎn)的子樹(shù)中是不是包含了另外一個(gè)結(jié)點(diǎn)。這不是件很難的事，我們可以用遞歸的方法來(lái)實(shí)現(xiàn)：

復(fù)制代碼代碼如下:

/*
// If the tree with head pHead has a node pNode, return true.
// Otherwise return false.
*/
bool HasNode(TreeNode* pHead, TreeNode* pNode)
{
 if(pHead == pNode)
  return true;
 bool has = false;
 if(pHead->m_pLeft != NULL)
  has = HasNode(pHead->m_pLeft, pNode);
 if(!has && pHead->m_pRight != NULL)
  has = HasNode(pHead->m_pRight, pNode);
 return has;
}

我們可以從根結(jié)點(diǎn)開(kāi)始，判斷以當(dāng)前結(jié)點(diǎn)為根的樹(shù)中左右子樹(shù)是不是包含我們要找的兩個(gè)結(jié)點(diǎn)。如果兩個(gè)結(jié)點(diǎn)都出現(xiàn)在它的左子樹(shù)中，那最低的共同父結(jié)點(diǎn)也出現(xiàn)在它的左子樹(shù)中。如果兩個(gè)結(jié)點(diǎn)都出現(xiàn)在它的右子樹(shù)中，那最低的共同父結(jié)點(diǎn)也出現(xiàn)在它的右子樹(shù)中。如果兩個(gè)結(jié)點(diǎn)一個(gè)出現(xiàn)在左子樹(shù)中，一個(gè)出現(xiàn)在右子樹(shù)中，那當(dāng)前的結(jié)點(diǎn)就是最低的共同父結(jié)點(diǎn)?；谶@個(gè)思路，我們可以寫(xiě)出如下代碼：

復(fù)制代碼代碼如下:

/*
// Find the last parent of pNode1 and pNode2 in a tree with head pHead
*/
TreeNode* LastCommonParent_1(TreeNode* pHead, TreeNode* pNode1, TreeNode* pNode2)
{
 if(pHead == NULL || pNode1 == NULL || pNode2 == NULL)
  return NULL;
 // check whether left child has pNode1 and pNode2
 bool leftHasNode1 = false;
 bool leftHasNode2 = false;
 if(pHead->m_pLeft != NULL)
 {
  leftHasNode1 = HasNode(pHead->m_pLeft, pNode1);
  leftHasNode2 = HasNode(pHead->m_pLeft, pNode2);
 } 
 if(leftHasNode1 && leftHasNode2)
 {
  if(pHead->m_pLeft == pNode1 || pHead->m_pLeft == pNode2)
   return pHead;
  return LastCommonParent_1(pHead->m_pLeft, pNode1, pNode2);
 }
 // check whether right child has pNode1 and pNode2
 bool rightHasNode1 = false;
 bool rightHasNode2 = false;
 if(pHead->m_pRight != NULL)
 {
  if(!leftHasNode1)
   rightHasNode1 = HasNode(pHead->m_pRight, pNode1);
  if(!leftHasNode2)
   rightHasNode2 = HasNode(pHead->m_pRight, pNode2);
 }
 if(rightHasNode1 && rightHasNode2)
 {
  if(pHead->m_pRight == pNode1 || pHead->m_pRight == pNode2)
   return pHead;
  return LastCommonParent_1(pHead->m_pRight, pNode1, pNode2);
 }
 if((leftHasNode1 && rightHasNode2) || (leftHasNode2 && rightHasNode1))
  return pHead; 
 return NULL;
}

接著我們來(lái)分析一下這個(gè)方法的效率。函數(shù)HasNode的本質(zhì)就是遍歷一棵樹(shù)，其時(shí)間復(fù)雜度是O(n)（n是樹(shù)中結(jié)點(diǎn)的數(shù)目）。由于我們根結(jié)點(diǎn)開(kāi)始，要對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)HasNode。因此總的時(shí)間復(fù)雜度是O(n^2)。
我們仔細(xì)分析上述代碼，不難發(fā)現(xiàn)我們判斷以一個(gè)結(jié)點(diǎn)為根的樹(shù)是否含有某個(gè)結(jié)點(diǎn)時(shí)，需要遍歷樹(shù)的每個(gè)結(jié)點(diǎn)。接下來(lái)我們判斷左子結(jié)點(diǎn)或者右結(jié)點(diǎn)為根的樹(shù)中是否含有要找結(jié)點(diǎn)，仍然需要遍歷。第二次遍歷的操作其實(shí)在前面的第一次遍歷都做過(guò)了。由于存在重復(fù)的遍歷，本方法在時(shí)間效率上肯定不是最好的。
前面我們提過(guò)如果結(jié)點(diǎn)中有一個(gè)指向父結(jié)點(diǎn)的指針，我們可以把問(wèn)題轉(zhuǎn)化為求兩個(gè)鏈表的共同結(jié)點(diǎn)?，F(xiàn)在我們可以想辦法得到這個(gè)鏈表。我們?cè)谶@里稍作變化即可：

復(fù)制代碼代碼如下:

/*
// Get the path form pHead and pNode in a tree with head pHead
*/
bool GetNodePath(TreeNode* pHead, TreeNode* pNode, std::list<TreeNode*>& path)
{
 if(pHead == pNode)
  return true; 
 path.push_back(pHead); 
 bool found = false;
 if(pHead->m_pLeft != NULL)
  found = GetNodePath(pHead->m_pLeft, pNode, path);
 if(!found && pHead->m_pRight)
  found = GetNodePath(pHead->m_pRight, pNode, path);
 if(!found)
  path.pop_back();
 return found;
}

由于這個(gè)路徑是從跟結(jié)點(diǎn)開(kāi)始的。最低的共同父結(jié)點(diǎn)就是路徑中的最后一個(gè)共同結(jié)點(diǎn)：

復(fù)制代碼代碼如下:

/*
// Get the last common Node in two lists: path1 and path2
*/
TreeNode* LastCommonNode
(
 const std::list<TreeNode*>& path1, 
 const std::list<TreeNode*>& path2
 )
{
 std::list<TreeNode*>::const_iterator iterator1 = path1.begin();
 std::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;
}

有了前面兩個(gè)子函數(shù)之后，求兩個(gè)結(jié)點(diǎn)的最低共同父結(jié)點(diǎn)就很容易了。我們先求出從根結(jié)點(diǎn)出發(fā)到兩個(gè)結(jié)點(diǎn)的兩條路徑，再求出兩條路徑的最后一個(gè)共同結(jié)點(diǎn)。代碼如下：

復(fù)制代碼代碼如下:

/*
// Find the last parent of pNode1 and pNode2 in a tree with head pHead
*/
TreeNode* LastCommonParent_2(TreeNode* pHead, TreeNode* pNode1, TreeNode* pNode2)
{
 if(pHead == NULL || pNode1 == NULL || pNode2 == NULL)
  return NULL;
 std::list<TreeNode*> path1;
 GetNodePath(pHead, pNode1, path1);
 std::list<TreeNode*> path2;
 GetNodePath(pHead, pNode2, path2);
 return LastCommonNode(path1, path2);
}

這種思路的時(shí)間復(fù)雜度是O(n)，時(shí)間效率要比第一種方法好很多。但同時(shí)我們也要注意到，這種思路需要兩個(gè)鏈表來(lái)保存路徑，空間效率比不上第一個(gè)方法。

您可能感興趣的文章: