首先給出五道關(guān)于二叉樹的面試題，題目很簡單，這里會給出簡單分析，具體代碼，這里只給出最優(yōu)解法。
◆找出二叉樹中最遠結(jié)點的距離
◆由前序遍歷和中序遍歷重建二叉樹
◆判斷一棵二叉樹是否為完全二叉樹
◆求二叉樹中兩個結(jié)點的最近公共祖先
◆將二叉搜索樹轉(zhuǎn)換成一個排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點，只能調(diào)整樹中結(jié)點指針的指向。
找出二叉樹中最遠結(jié)點的距離
首先需要考慮一下，二叉樹中什么距離是最遠距離。以根節(jié)點為軸，左右子樹的大深度？當(dāng)然這只是一部分。準確地說，大深度是以根節(jié)點為軸，左右子樹的大深度之和與以各個子樹的根節(jié)點為軸左右子樹的大深度之和的較大值。
雖然有點繞，看下圖就會明白。
思路一：解決這個問題最直接的方式就是遍歷。對每個結(jié)點求深度，之后再與保存的大深度max_depth進行對比，但對于O(n^2)的時間復(fù)雜度，我們還是選擇能避免就避免，這應(yīng)該是一種比較糟糕的時間復(fù)雜度。
思路二：針對思路一，可以發(fā)現(xiàn)，我們重復(fù)了大量的遍歷工作。對每一個結(jié)點求深度，對最深的一個結(jié)點遍歷了n^2次，沒有線索化過的二叉樹遍歷，最常用的是遞歸方法，因此，我們可以僅僅通過一次遞歸，同時得到該結(jié)點的深度和以該節(jié)點為根的子樹的大距離。當(dāng)然，由于深度是相對整個遍歷過程的，因此在遞歸過程中，它應(yīng)該是以引用的方式進行傳遞，我們這里不需要將深度也作為一個參數(shù)進行傳遞，原因很簡單，深度完全可以在遞歸的時候用返回值接收，這也解決了對左右子樹深度的比較選取的過程中多余創(chuàng)建出的變量。
重慶分公司
重慶分公司
int MaxDistance()
{
if (_root == NULL)
return 0;
int max = 0;
_MaxDistance(_root, max);
return max;
}
int _MaxDistance(Node* cur, int& max) // 只返回深度
{
if (cur == NULL)
return 0;
int leftDepth = _MaxDistance(cur->_left, max);
int rightDepth = _MaxDistance(cur->_right, max);
if (leftDepth + rightDepth > max)
max = leftDepth + rightDepth;
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}代碼看上去很簡單，這里巧妙之處在于在MaxDistance()函數(shù)中，我們沒有用它調(diào)用的_MaxDistance()函數(shù)的返回值，該函數(shù)返回值的作用，僅僅是為了提供遞歸返回使用。我們需要的max_distance是通過傳遞引用的方式獲取的。
由前序遍歷和中序遍歷重建二叉樹
這道題應(yīng)該是網(wǎng)上做爛的題目，這里只是重新提一下，因為它并沒有什么建檔方法可言。
我們需要考慮，前、中、后序遍歷三種方式遍歷結(jié)果有什么特點。
前序遍歷：第一個元素必然是根節(jié)點，擴展一點將，如果我們從前序遍歷的序列中取出的一段屬于某個子樹的前序遍歷段，那么該子序列的第一個結(jié)點也將是該子樹的根節(jié)點。
中序遍歷：中序遍歷由于是先左后根，最后再右的順序，因此，當(dāng)我們知道某個結(jié)點為跟結(jié)點的話，那么它的左右兩側(cè)分別是左子樹和右子樹的中序遍歷序列。同上，也擴展一點將，只要可以找到某一段子樹中序遍歷序列的根節(jié)點，那么該序列中，跟結(jié)點的左右兩側(cè)序列也是該子樹的左右子樹。
后續(xù)遍歷：后續(xù)遍歷的特點是遍歷完左右結(jié)點之后再遍歷跟結(jié)點。和前序遍歷的區(qū)別就在于把根節(jié)點放到了最后訪問，因此，兩種遍歷的結(jié)果類似，只不過需要從后向前依次取元素。也就是說，最后一個元素，是當(dāng)前樹的根節(jié)點。
經(jīng)過上面的分析，我們可以得出一個這樣的結(jié)論，如果我們想重建二叉樹，我們至少需要兩種遍歷的序列，而且必須要有中序遍歷序列。
接下來我們討論如何利用前序和中序遍歷的結(jié)果重建二叉樹。大致可分為以下四步：
1. 用前序序列的第一個結(jié)點作為根結(jié)點;
2. 在中序序列中查找根結(jié)點的位置，并以此為界將中序序列劃分為左、右兩個序列(左、右子樹);
3. 根據(jù)左、右子樹的中序序列中的結(jié)點個數(shù)，將前序序列去掉根結(jié)點后的序列劃分為左、右兩個序列，它們分別是左、右子樹的前序序列;
4. 對左、右子樹的前序序列和中序序列遞歸地實施同樣方法，直到所得左、右子樹為空。
下來看實現(xiàn)代碼。
typedef BinaryTreeNodeNode; Node* ReBuildTree(const string preorder, const string inorder) { if (preorder.empty()) return NULL; char root_value = preorder[0]; Node* node = new Node(root_value); size_t index = inorder.find(root_value); string left_preorder = preorder.substr(1, index); string left_inorder = inorder.substr(0, 3); string right_preorder = preorder.substr(index + 1, preorder.size() - index - 1); string right_inorder = inorder.substr(index + 1, inorder.size() - index - 1); node->_left = ReBuildTree(left_preorder, left_inorder); node->_right = ReBuildTree(right_preorder, right_inorder); return node; } void InOrder(Node* node) { if (node == NULL) return; InOrder(node->_left); cout << node->_data << " "; InOrder(node->_right); }
仔細觀察可以發(fā)現(xiàn)，這里使用的容器是string，我這里選用string作為容器，是因為string有自帶的查找某個元素的功能，同時可以實現(xiàn)部分截取，方便構(gòu)建子序列，缺點就是每個結(jié)點中key的類型只能是字符。當(dāng)然，這里也可以選用vector等其他容器，只不過vector沒有內(nèi)置的Find函數(shù)，因此在中序遍歷序列中找根節(jié)點的時候需要進行遍歷，vector構(gòu)建子序列時也并不復(fù)雜，可以通過迭代器區(qū)間直接構(gòu)造一個vector對象。這里點到為止。
判斷一棵二叉樹是否為完全二叉樹
首先需要知道的是什么是滿二叉樹。若設(shè)二叉樹的深度為h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點數(shù)都達到大個數(shù)，第 h 層所有的結(jié)點都連續(xù)集中在最左邊，這就是完全二叉樹。
判斷一棵樹是不是滿二叉樹，就不能再像之前那樣，遞歸去遍歷，因為遞歸是在走深度，所以解決這一問題，需要借助queue完成層序遍歷。
我們簡單的層序遍歷是先將根節(jié)點入隊列，之后依次訪問隊列的front結(jié)點，訪問完成，將front結(jié)點pop，同時將左右不為空的子節(jié)點入隊列，直到隊列為空。這一點應(yīng)該沒有太大問題。回想一下，我們在簡單層序遍歷的時候，注意了什么問題？如果子結(jié)點為NULL，則不入隊列，防止下次對空結(jié)點進行訪問 。
回到我們一開始的問題，判斷一棵二叉樹是否為滿二叉樹。這里在簡單層序遍歷上做一些處理，先不考慮隊列的問題，當(dāng)我們簡單地在走層序遍歷過程中，當(dāng)碰到一個結(jié)點為NULL時，如果之后都是空結(jié)點，那么該二叉樹為完全二叉樹，否則，不滿足完全二叉樹。
因此，要實現(xiàn)這個邏輯，就不能只是簡單地把非空結(jié)點入隊列，所有結(jié)點都需要入隊列，當(dāng)front變?yōu)镹ULL時，表示讀取到了一個空結(jié)點，此時，它的子節(jié)點之前的所有結(jié)點都已經(jīng)入隊列，當(dāng)隊列中還存在空結(jié)點，則該樹不滿足滿二叉樹。
代碼實現(xiàn)如下：
bool IsFullBinaryTree()
{
if (_root == NULL)
return true;
queue que;
que.push(_root);
Node* front = NULL;
while (front = que.front())
{
que.push(front->_left);
que.push(front->_right);
que.pop();
}
while (!que.empty())
{
if (que.front() != NULL)
return false;
que.pop();
}
return true;
} 求二叉樹中兩個結(jié)點的最近公共祖先
第一次看到這道題，感覺無從下手，后來仔細想想，不是廢話么，只告訴了要找最近公共祖先，二叉樹的特點都不知道，怎么找......沒辦法，分情況看。
情況一：搜索二叉樹
這應(yīng)該是最簡單的情況了，搜索二叉樹始終滿足根結(jié)點大于左孩子，小于右孩子。那他們的公共祖先的key值就必然介于兩個結(jié)點之間。即
(root->_data >= node1->_data && root->_data <= node2->_data) ||(root->_data >= node2->_data && root->_data <= node1->_data)
因此，這樣一來就簡單了很多，代碼實現(xiàn)如下：
typedef SearchTreeNodeNode; Node* FindParent_SearchTree(Node* node1, Node* node2, Node* root) { if (root == NULL) return NULL; if (node1 == NULL) return node2; if (node2 == NULL) return node1; while (1) { if(root === NULL) assert(false); if ((root->_data >= node1->_data && root->_data <= node2->_data) || (root->_data >= node2->_data && root->_data <= node1->_data)) { return root; } else if (root->_data > node1->_data) root = root->_left; else root = root->_right; } }
最開始的判斷條件是為了防止BUG的出現(xiàn)的。因為這種做法有個缺陷，如果兩個結(jié)點不再樹中呢？但是再想一想，我傳遞的參數(shù)是 Node* ，該結(jié)點一定是通過Find()函數(shù)或其他可以返回Node* 類型的函數(shù)返回的，如果不存在某個結(jié)點，這里參數(shù)傳遞一定是NULL，因此這里添加了if判斷。
情況二：帶父指針的二叉樹
如果說一個該二叉樹結(jié)構(gòu)中有父指針，那么這道題處理起來就應(yīng)該容易的多。有父指針，意味著我可以從下向上去遍歷，沿著父節(jié)點的路徑直到走到根節(jié)點。那問題就轉(zhuǎn)化為求兩個單鏈表的交點CrossNode。
求解單鏈表的交點解法有兩種，一就是對兩個單鏈表進行遍歷并求出長度，然后再重新遍歷，第二次遍歷時，較長的單鏈表的指針要先走長度差次，當(dāng)兩個指針相同時，表明相遇，如果走到NULL，則只有一種情況，這兩個結(jié)點不在一棵樹內(nèi)。第二種方法就是構(gòu)建環(huán)。讓根節(jié)點的父指針parent指向其中一個結(jié)點，以另一個結(jié)點為頭，判斷鏈表是否帶環(huán)。
這里給出通過找交點找到最近公共結(jié)點的代碼：
Node* NearestParent(Node* Node1, Node* Node2)
{
if (_root == NULL)
return NULL;
if (Node1 == NULL || Node2 == NULL)
assert(false);
int length2 = 0;
int length3 = 0;
Node* cur1 = Node1;
Node* cur2 = Node2;
while (cur1 != NULL)
{
length2++;
cur1 = cur1->_parent;
}
while (cur2 != NULL)
{
length3++;
cur2 = cur2->_parent;
}
Node* long_List = NULL;
Node* short_List= NULL;
if (length2 > length3)
{
long_List = Node1;
short_List = Node2;
}
else // length2 <= length3
{
long_List = Node2;
short_List = Node1;
}
int distance = abs(length2 - length3);
while (distance--)
{
long_List = long_List->_parent;
}
while (long_List != NULL)
{
if (long_List == short_List)
return long_List;
long_List = long_List->_parent;
short_List = short_List->_parent;
}
return NULL;
}情況三：任意一棵不帶父節(jié)點的二叉樹
這種情況應(yīng)該是最復(fù)雜的。
這里給出一種新思路，應(yīng)該很少用過的。在C++里面，有個結(jié)構(gòu)體叫pair，是庫里封裝好的，提供了兩個成員，通過這種方式，我們可以一次返回多個值。給出pair的定義。
