二叉樹經典面試題

    首先給出五道關于二叉樹的面試題，題目很簡單，這里會給出簡單分析，具體代碼，這里只給出最優解法。

    ◆找出二叉樹中最遠結點的距離

    ◆由前序遍歷和中序遍歷重建二叉樹

    ◆判斷一棵二叉樹是否為完全二叉樹

    ◆求二叉樹中兩個結點的最近公共祖先

    ◆將二叉搜索樹轉換成一個排序的雙向鏈表。要求不能創建任何新的結點，只能調整樹中結點指針的指向。

找出二叉樹中最遠結點的距離

    首先需要考慮一下，二叉樹中什么距離是最遠距離。以根節點為軸，左右子樹的最大深度？當然這只是一部分。準確地說，最大深度是以根節點為軸，左右子樹的最大深度之和與以各個子樹的根節點為軸左右子樹的最大深度之和的較大值。

    雖然有點繞，看下圖就會明白。

    思路一：解決這個問題最直接的方式就是遍歷。對每個結點求深度，之后再與保存的最大深度max_depth進行對比，但對于O(n^2)的時間復雜度，我們還是選擇能避免就避免，這應該是一種比較糟糕的時間復雜度。

    思路二：針對思路一，可以發現，我們重復了大量的遍歷工作。對每一個結點求深度，對最深的一個結點遍歷了n^2次，沒有線索化過的二叉樹遍歷，最常用的是遞歸方法，因此，我們可以僅僅通過一次遞歸，同時得到該結點的深度和以該節點為根的子樹的最大距離。當然，由于深度是相對整個遍歷過程的，因此在遞歸過程中，它應該是以引用的方式進行傳遞，我們這里不需要將深度也作為一個參數進行傳遞，原因很簡單，深度完全可以在遞歸的時候用返回值接收，這也解決了對左右子樹深度的比較選取的過程中多余創建出的變量。

       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()函數中，我們沒有用它調用的_MaxDistance()函數的返回值，該函數返回值的作用，僅僅是為了提供遞歸返回使用。我們需要的max_distance是通過傳遞引用的方式獲取的。

由前序遍歷和中序遍歷重建二叉樹

    這道題應該是網上做爛的題目，這里只是重新提一下，因為它并沒有什么建檔方法可言。

    我們需要考慮，前、中、后序遍歷三種方式遍歷結果有什么特點。

    前序遍歷：第一個元素必然是根節點，擴展一點將，如果我們從前序遍歷的序列中取出的一段屬于某個子樹的前序遍歷段，那么該子序列的第一個結點也將是該子樹的根節點。

    中序遍歷：中序遍歷由于是先左后根，最后再右的順序，因此，當我們知道某個結點為跟結點的話，那么它的左右兩側分別是左子樹和右子樹的中序遍歷序列。同上，也擴展一點將，只要可以找到某一段子樹中序遍歷序列的根節點，那么該序列中，跟結點的左右兩側序列也是該子樹的左右子樹。

    后續遍歷：后續遍歷的特點是遍歷完左右結點之后再遍歷跟結點。和前序遍歷的區別就在于把根節點放到了最后訪問，因此，兩種遍歷的結果類似，只不過需要從后向前依次取元素。也就是說，最后一個元素，是當前樹的根節點。

    經過上面的分析，我們可以得出一個這樣的結論，如果我們想重建二叉樹，我們至少需要兩種遍歷的序列，而且必須要有中序遍歷序列。

    接下來我們討論如何利用前序和中序遍歷的結果重建二叉樹。大致可分為以下四步： 

1. 用前序序列的第一個結點作為根結點;

2. 在中序序列中查找根結點的位置，并以此為界將中序序列劃分為左、右兩個序列(左、右子樹);

3. 根據左、右子樹的中序序列中的結點個數，將前序序列去掉根結點后的序列劃分為左、右兩個序列，它們分別是左、右子樹的前序序列;

4. 對左、右子樹的前序序列和中序序列遞歸地實施同樣方法，直到所得左、右子樹為空。

    下來看實現代碼。

typedef BinaryTreeNode<char> Node;
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);
}

    仔細觀察可以發現，這里使用的容器是string，我這里選用string作為容器，是因為string有自帶的查找某個元素的功能，同時可以實現部分截取，方便構建子序列，缺點就是每個結點中key的類型只能是字符。當然，這里也可以選用vector等其他容器，只不過vector沒有內置的Find函數，因此在中序遍歷序列中找根節點的時候需要進行遍歷，vector構建子序列時也并不復雜，可以通過迭代器區間直接構造一個vector對象。這里點到為止。

判斷一棵二叉樹是否為完全二叉樹

    首先需要知道的是什么是滿二叉樹。若設二叉樹的深度為h，除第 h 層外，其它各層 (1～h-1) 的結點數都達到最大個數，第 h 層所有的結點都連續集中在最左邊，這就是完全二叉樹。

    判斷一棵樹是不是滿二叉樹，就不能再像之前那樣，遞歸去遍歷，因為遞歸是在走深度，所以解決這一問題，需要借助queue完成層序遍歷。    

    我們簡單的層序遍歷是先將根節點入隊列，之后依次訪問隊列的front結點，訪問完成，將front結點pop，同時將左右不為空的子節點入隊列，直到隊列為空。這一點應該沒有太大問題。回想一下，我們在簡單層序遍歷的時候，注意了什么問題？如果子結點為NULL，則不入隊列，防止下次對空結點進行訪問 。

    回到我們一開始的問題，判斷一棵二叉樹是否為滿二叉樹。這里在簡單層序遍歷上做一些處理，先不考慮隊列的問題，當我們簡單地在走層序遍歷過程中，當碰到一個結點為NULL時，如果之后都是空結點，那么該二叉樹為完全二叉樹，否則，不滿足完全二叉樹。

    因此，要實現這個邏輯，就不能只是簡單地把非空結點入隊列，所有結點都需要入隊列，當front變為NULL時，表示讀取到了一個空結點，此時，它的子節點之前的所有結點都已經入隊列，當隊列中還存在空結點，則該樹不滿足滿二叉樹。

代碼實現如下：

            bool IsFullBinaryTree()
            {
                        if (_root == NULL)
                                    return true;
                        queue<Node*> 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;
            }

求二叉樹中兩個結點的最近公共祖先

    第一次看到這道題，感覺無從下手，后來仔細想想，不是廢話么，只告訴了要找最近公共祖先，二叉樹的特點都不知道，怎么找......沒辦法，分情況看。

    情況一：搜索二叉樹

    這應該是最簡單的情況了，搜索二叉樹始終滿足根結點大于左孩子，小于右孩子。那他們的公共祖先的key值就必然介于兩個結點之間。即

    (root->_data >= node1->_data && root->_data <= node2->_data)
  ||(root->_data >= node2->_data && root->_data <= node1->_data)

    因此，這樣一來就簡單了很多，代碼實現如下：

typedef SearchTreeNode<int> Node;
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的出現的。因為這種做法有個缺陷，如果兩個結點不再樹中呢？但是再想一想，我傳遞的參數是 Node* ，該結點一定是通過Find()函數或其他可以返回Node* 類型的函數返回的，如果不存在某個結點，這里參數傳遞一定是NULL，因此這里添加了if判斷。

    情況二：帶父指針的二叉樹 

    如果說一個該二叉樹結構中有父指針，那么這道題處理起來就應該容易的多。有父指針，意味著我可以從下向上去遍歷，沿著父節點的路徑直到走到根節點。那問題就轉化為求兩個單鏈表的交點CrossNode。

    求解單鏈表的交點解法有兩種，一就是對兩個單鏈表進行遍歷并求出長度，然后再重新遍歷，第二次遍歷時，較長的單鏈表的指針要先走長度差次，當兩個指針相同時，表明相遇，如果走到NULL，則只有一種情況，這兩個結點不在一棵樹內。第二種方法就是構建環。讓根節點的父指針parent指向其中一個結點，以另一個結點為頭，判斷鏈表是否帶環。

    這里給出通過找交點找到最近公共結點的代碼：

        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;
       }

    情況三：任意一棵不帶父節點的二叉樹

    這種情況應該是最復雜的。

    這里給出一種新思路，應該很少用過的。在C++里面，有個結構體叫pair，是庫里封裝好的，提供了兩個成員，通過這種方式，我們可以一次返回多個值。給出pair的定義。

template<classT1,classT2>structpair
{typedefT1 first_type;typedefT2 second_type;

  T1 first;
  T2 second;
  pair() : first(T1()), second(T2()) {}
}

    給這個東西有什么用呢？

    繼續回到我們一開始的問題。我們要找兩個結點的最近父節點。當然一層嵌套一層地遍歷二叉樹也有可能得出結果，但效率太低，至少是O(n^2)的時間復雜度。我們得到什么信息的時候，可以確定一個結點是他們的公共祖先？如果我們可以得到信息，在該結點的左右子樹中找到了兩個結點，那這個結點一定是他們的父節點（先不考慮是否為最近）。

    換句話說，我們需要在一個結點出得到的信息，應該是在它的左右子樹中遍歷到的兩個結點的個數。同時因為要采用的是遞歸遍歷，因此我們需要返回該結點。怎么解決“最近”的問題呢？遞歸給我們提供了方便，只要在一開始進行一次判斷即可。

    代碼實現如下：

     Node* NearestParent(Node* Node1, Node* Node2)
       {
             if (_root == NULL)
                    return NULL;
             if (Node1 == NULL || Node2 == NULL)
                    assert(false);
             pair<Node*, int> ret = NodeNearestParent(_root, Node1, Node2);
             return ret.first;
       }
       
       pair<Node*, int> NodeNearestParent(Node* root, Node* node1, Node* node2)
       {
             if (root == NULL)
                    return pair<Node*, int>(NULL, 0);
             pair<Node*, int> left_pair = NodeNearestParent(root->_left, node1, node2);
             pair<Node*, int> right_pair = NodeNearestParent(root->_right, node1, node2);
             if (left_pair.second == 2)
                    return left_pair;
             if (right_pair.second == 2)
                    return right_pair;
             int x = 0;
             if (root == node1 || root == node2)
                    x = 1;
             return pair<Node*, int>(root, left_pair.second + right_pair.second + x);
       }

    pair結構題中保存的兩個對象，第一個是當前結點，另外一個是在它左右子樹中找到的兩個結點個數，當然包括了它自己。一旦當某次發現，該結點的second為2時，表明該結點就是我們要找的最近父結點。這里采用的依舊是后續遍歷的方式。

將二叉搜索樹轉換成一個排序的雙向鏈表。要求不能創建任何新的結點，只能調整樹中結點指針的指向。

    這道題應該和二叉樹的線索化類似，不過有一點不同的是，線索化只是針對空結點而言的，只有當二叉樹中某個指針為空，才需要改變它的指向。

    對于二叉搜索樹而言，它的中序遍歷序列就是有序的，因此，這里依舊采用的是中序遍歷來改變它。將二叉樹轉換為雙向鏈表，其實就是讓左孩子指針指向該結點的前一個結點，右孩子指針指向下一個結點。因此遍歷的時候，需要兩個指針，prev和cur。

    還有一點需要注意，轉換為雙向鏈表之后，二叉樹的結構即不復存在，我們就不能再通過根節點去遍歷二叉樹，因此這里在將二叉樹轉換為雙向鏈表之前，首先要做的是保存它的最左結點，因為它的最左結點是雙向鏈表的頭結點。

    代碼實現如下：

         Node* BinaryTreeToList()
            {
                        if (_root == NULL)
                                    return NULL;
                        Node* head = _root;
                        while (head->_left != NULL)
                        {
                                    head = head->_left;
                        }
                        Node* prev = NULL;
                        _Translate(_root, prev);
                        return head;
            }
            void _Translate(Node* root, Node*& prev) // prev要傳遞引用
            {
                        if (root == NULL)
                                    return;
                        _Translate(root->_left, prev);
                        root->_left = prev;
                        if (prev)
                                    prev->_right = root;
                        prev = root;
                        _Translate(root->_right, prev);
            }

    這就是這五道面試題，解題思路和代碼已經給出。可以發現，遞歸是降低二叉樹時間復雜度的有效方式，時間復雜度一般可以用O(n^2)降低到O(n)，缺點就是帶來了O(logN)的空間復雜度，logN是非常小的復雜度，相對來說，遞歸解決二叉樹在絕大多數情況下，是一種相對較為優的解法。

    同時，這里加入了一種新的思想，就是pair，如何給pair的兩個成員分配合理的類型和功能，這個是需要考慮的問題，但不得不說，有些情況下，pair可以帶來意想不到的效果。