// # -*- coding:utf-8 -*- // # @Author: Mr.chen(ai-chen2050@qq.com) // # @Date: 2018-08-17 16:32:55 // 注：此為第三彈，主要講解樹（但是面試中大多提到的都是二叉樹）相關面試筆試題，要求手寫。 // 在樹的面試題中也會涉及到大量的指針，對于二叉樹來說最應該先關注的就是它的前中后序遍歷， // 對于它們來說都有遞歸和非遞歸遍歷，還有層次遍歷，說明如下圖所示：

?

? ? ?

? ? ? ?

/* 1、重建二叉樹,輸入某二叉樹的前序和中序，請重建該二叉樹。假設輸入的前序和中序序列都不含重復的數字，例如輸入前序的序列為{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6} 思路：首先前序序列中的第一個節點一定是根節點,中序序列中,根節點在中間,其左右子樹在其兩邊，故我們可以根據中序找到根節點，左邊的即為左子樹，右邊的即為右左子樹,之后再其左右兩邊的序列遞歸去構造生成二叉樹。代碼如下： */#include<iostream> #include<set> #include<map> #include<stack> #include<deque> #include<list> #include<stdexcept>using namespace std;// 二叉樹的節點結構體為：如下。 struct BiTreeNode {int m_value;BiTreeNode* m_pLeft;BiTreeNode* m_pRight; };BiTreeNode* Construct(int* preOrder,int* inOrder,int length) {if(preOrder == NULL || inOrder == NULL || length <= 0)return NULL;return ConstructCore(preOrder,preOrder+length-1,inOrder,inOrder+length-1); }BiTreeNode* ConstructCore(int* sPreOrder,int* ePreOrder,int* sInOrder,int* eInOrder) {// 前序遍歷的第一個節點是根節點的值int rootValue = sPreOrder[0];BiTreeNode* root = new BiTreeNode();root->m_value = rootValue;root->m_pLeft = root->m_pRight = NULL;// 定義遞歸出口if(sPreOrder == ePreOrder){if(sInOrder == eInOrder && *sPreOrder == *sInOrder)return root;else throw std::exception("Invalid input.");}// 在中序中找到根節點的值int* rootInOrder = sInOrder;while(rootInOrder < eInOrder && *rootInOrder != rootValue)++ rootInOrder;if(rootInOrder == eInOrder && *rootInOrder != rootValue)throw std::exception("Invalid input...")// 左子樹的節點個數int leftLength = rootInOrder - sInOrder;int* leftPreOrderEnd = sPreOrder + leftLength;if(leftLength > 0) //構建左子樹 root->m_pLeft = ConstructCore(sPreOrder + 1,leftPreOrderEnd,sInOrder,rootInOrder - 1);if(leftLength < ePreOrder - sPreOrder) //構建右子樹root->m_pRight = ConstructCore(leftPreOrderEnd+1,ePreOrder,rootInOrder+1,eInOrder)return root; }/* 2、求二叉樹的深度：輸入一顆二叉樹的根節點，求該樹的深度。從根節點到頁節點依次經過的節點（含根和葉節點）形成樹的一顆路徑,最長路徑的長度即為樹的深度。思路：我們可以從另外一個角度來考慮樹的深度。如果樹只有一個節點,則深度為 1,如果根節點只有左子樹而沒有右子樹，則樹的深度應該是左子樹加 1，反之,是右子樹加 1,故我們很容易想到遞歸實現。 */ int treeDepth(BiTreeNode* pRoot) {if(NULL == pRoot)return 0;// 計算左右子樹的深度int nLeft = treeDepth(pRoot->m_pLeft);int nRight = treeDepth(pRoot->m_pRight);return nLeft > nRight? (nLeft + 1):(nRight + 1); }/* 2.1 面試官加深難度, 追問: 輸入一顆二叉樹的根節點，判斷它是不是平衡二叉樹,如果某二叉樹中任意節點的左右子樹深度相差不超過 1,那么它就是一顆平衡二叉樹。法一：需要重復遍歷一個節點多次，基于上述代碼的改進，法二：采用后序遍歷的方法遍歷每一個節點，在遍歷一個節點之前，我們就已經遍歷了該節點的左右子樹。只要在遍歷一個節點的時候，記錄它的深度，就可以一邊遍歷，一邊判斷該節點是否平衡的了。 *///法一：需要重復遍歷一個節點多次 bool isBalanced(BiTreeNode* pRoot) {if(NULL == pRoot)return true;int left = treeDepth(pRoot->m_pLeft);int right = treeDepth(pRoot->m_pRight);int diff = left - right;if(diff > 1 || diff < -1)return false;// 遞歸判斷，左右子樹return isBalanced(pRoot->m_pLeft) && isBalanced(pRoot->m_pRight); } // 由于重復遍歷會影響性能，故我們推薦下面這種基于后序遍歷的方法。// 法二：每個節點只遍歷一次 bool isBalanced(BiTreeNode* pRoot,int* pDepth) {if(NULL == pRoot){*pDepth = 0;return true;}int left,right;if(isBalanced(pRoot->m_pLeft, &left) && isBalanced(pRoot->m_pRight, &right)){int diff = left - right;if(diff <= 1 && diff >= -1){*pDepth = 1 + (left > right? left:right );return true;}}return false; }// 調用時，只需給上面的函數傳入一個二叉樹的根節點和表示節點深度的整形變量即可。 bool isBalancedTree(BiTreeNode* pRoot) {int depth = 0;return isBalanced(pRoot, &depth); } /* 3、樹的子結構,題目：輸入兩顆二叉樹 A 和 B,判斷 B 是不是 A 的子結構，子結構定義如下圖:一般來說，樹的指針的操作比起鏈表來說更多，如果面試官想加大難度，則會考察樹，在涉及二叉樹的題目中，由于涉及到很多的指針操作，故一定要注意檢查邊界條件，即檢查空指針，如果沒有檢查，而導致程序崩潰，則是很尷尬和忌諱的事情。故在操作指針時，一定要注意這個指針是不是為 NULL,如果是，該怎么處理。本題可以分兩步來看，第一步是從樹 A 中查找與根節點值一樣的節點,實際上是對樹的遍歷，一般遍歷樹可以有遞歸和迭代循環，一般遞歸代碼較為簡單，一般會優先考慮，第二步是判斷 A 樹中以 R 為根節點的子樹是不是和樹 B 具有相同的結構，同樣，我們也可以采用遞歸的方法來做。 */

? ? ? ? ? ??

// 第一步: 遞歸遍歷，尋找相同節點 bool hasSubTree(BiTreeNode* pRoot1,BiTreeNode* pRoot2) {bool result = false;// 異常值檢測if(NULL != pRoot1 && NULL != pRoot2){if(pRoot1->m_value == pRoot2->m_value)result = doseTree1HasTree2(pRoot1,pRoot2);if(!result)result = hasSubTree(pRoot1->m_pLeft,pRoot2);if(!result)result = hasSubTree(pRoot1->m_pRight,pRoot2);}return result; }// 第二步：比較子結構，同樣可以用遞歸的方法 bool doseTree1HasTree2(BiTreeNode* pRoot1,BiTreeNode* pRoot2) {// 定義遞歸出口if(NULL == pRoot2)return true;if(NULL == pRoot1)return false;if(pRoot1->m_value != pRoot2->m_value)return false;return doseTree1HasTree2(pRoot1->m_pLeft,pRoot2->m_pLeft) &&doseTree1HasTree2(pRoot1->m_pRight,pRoot2->m_pRight); } /* 4、二叉樹的鏡像(畫圖(幾何的視角去看待)讓抽象問題形象化),二叉樹的鏡像對大多數沒有接觸過得人來說，算是一個新的感念,此時可以通過幾何畫圖的方式來讓問題明朗化。如下圖：通過觀察圖，我們來總結解決該問題的方法。首先交換根節點的兩個子節點，此時子節點的子節點的左右子樹的相對關系保持不變。故還需要交換子節點的子節點的左右子樹，知道葉子節點。思路如下圖，所示。通過前序遍歷這棵樹的每個節點，如果該節點有子節點，就交換該節點的兩個子節點，當交換完所有的非葉子節點的左右子節點后，就得到了樹的鏡像。 */

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

? ? ? ? ? ? ? ? ? ? ? ?解題思路圖，如下：?

? ? ? ? ? ? ? ?

void mirrorRecursively(BiTreeNode* pRoot) {// 定義遞歸出口if(pRoot == NULL || (pRoot->m_pLeft == NULL && pRoot->m_pRight == NULL))return;// 首先交換根節點BiTreeNode* pTemp = pRoot->m_pLeft;pRoot->m_pLeft = pRoot->m_pRight;pRoot->m_pRight = pTemp;// recursivelyif(pRoot->m_pLeft)mirrorRecursively(pRoot->m_pLeft);if(pRoot->m_pRight)mirrorRecursively(pRoot->m_pRight) }// 當使用循環時，需要一個棧來保存遍歷到的當前的根結點 void mirrorCircularly(BiTreeNode* pRoot) {// 用棧保存根結點std::stack<BiTreeNode* > stackRoot;if(pRoot == NULL)return;stackRoot.push(pRoot);// 開始循環while(!stackRoot.empty()){//從棧中獲取根結點BiTreeNode* pNode = stackRoot.top();stackRoot.pop();// 首先交換根節點BiTreeNode* pTemp = pNode->m_pLeft;pNode->m_pLeft = pNode->m_pRight;pNode->m_pRight = pTemp;if(pNode->m_pLeft)stackRoot.push(pNode->m_pLeft);if(pNode->m_pRight)stackRoot.push(pNode->m_pRight);} }/* 5、從上到下打印二叉樹，從上到下打印二叉樹的每一個節點，同一層的節點按照從左到右的順序打印。即層次遍歷。其實，樹是一種簡化的圖，該題也對應圖的廣度優先遍歷。我們來嘗試分析一下，由于是層次遍歷，故最先打印頭結點,然后我們需要一個容器來保存頭結點的兩個子節點，并且是先左后右，且容器應該保證先進先出（隊列）,之后只要隊列里面的節點有孩子節點，我們就應該將孩子節點加載到隊列末尾,以便后續遍歷。直到葉子節點。 */// 由于 STL 已經幫我們實現了一個很好的雙端隊列 deque,故我們這里直接采用 deque 作為數據結構 void printFromTopToButtom(BiTreeNode* pRoot) {if(NULL === pRoot)return;std::deque<BiTreeNode* > treeDeque;// 壓入根節點treeDepth.push_back(pRoot);// 循環迭代while(treeDeque.size()){BiTreeNode* pNode = treeDeque.front();treeDeque.pop_front();std::cout<< pNode->m_value <<std::endl;// 將 pNode 的子節點加入隊列if(pNode->m_pLeft)treeDeque.push_back(pNode->m_pLeft);if(pNode->m_pRight)treeDeque.push_back(pNode->m_pRight);} } // 本題的擴展圖的廣度優先遍歷/* 6、二叉搜索樹的后序遍歷序列，題目：輸入一個整數數組，判斷該數組是不是某二叉搜索樹的后序遍歷結果。如果是返回True, 不是返回False,假設輸入的兩個數組的任意兩個數字都不相同。分析：特殊的地方是二叉搜索樹是具有排序屬性的（左子樹小于根節點，根節點小于右子樹）,加上后序遍歷,故我們需要分析出它的背后的規律。在后序遍歷中,最后一個數字是樹的根節點的值,數組中前面的數字可以分為兩部分，第一部分是左子樹節點的值，他們都比根節點小；第二部分是右子節點的值，它們都比根節點大。接下來用同樣的方法，確定于數組每一部分對應子樹的結構。這其實是一個遞歸的過程。 */// 找到規律后再寫代碼，就容易多了。 bool verifySquenceOfBST(int sequence[],int length) {if(sequence == NULL || length <= 0)return false;// 后序遍歷最后一個節點就是根節點int root = sequence[length-1];//找到左子樹的序列，在二叉搜索樹中,左子樹的節點小于根節點int i = 0;for(; i< length-1; ++i){if(sequence[i] > root)break;}//在二叉搜索樹中,右子樹的節點大于根節點int j = i;for(; j<length-1; ++j){if(sequence[j] < root)return false;}// 判斷左子樹是不是二叉搜索樹bool left = true;if(i>0)left = verifySquenceOfBST(sequence,i);// 判斷右子樹是不是二叉搜索樹bool right = true;if(i < length-1)right = verifySquenceOfBST(sequence+i, length - i +1);return left && right; }/* 7、二叉樹中和為某一個值的路徑,題目：輸入一個二叉樹和一個整數，打印出二叉樹中節點值的和為輸入整數的所有路徑。從樹的根節點開始往下一直到葉節點所經過的節點形成一條路徑。事例，如下圖,對于樹的路徑和這樣一個新概念，很難一下想到完整的思路,故可以先從一兩個具體的例子入手,尋找規律。首先加和是從根到葉子,故即遍歷中,只有前序遍歷是先根節點,故應該是前序遍歷,其次具體思路可也參見下圖說明。這個題明顯是所謂的回溯搜索的過程，參見 labuladong 算法小抄。此外應為要輸出整條路徑，所以需要將之前遍歷過得節點保存下來，這里采用 vector. 在遍歷完，不滿足條件后需要回溯，即進行逆操作。 */

? ? ? ? ? ? ? ? ?

? ? ? ? ? ? ? ? ??

? ? ? ? ? ? ? ? ? ?

? ? ? ? ? ? ? ? ? ? ?

? ? ? ? ? ? ? ? ?

void findPath(BiTreeNode* pRoot,int expectedSum) {if(pRoot == NULL)return;// 用 vector 模擬 stackstd::vector<int> path;int currentSum = 0;FindPath(pRoot,expectedSum,path,currentSum); }void FindPath(BiTreeNode* pRoot,int expectedSum,std::vector<int>& path,int &currentSum) {// 加入根節點的值，壓入棧currentSum += pRoot->m_value;path.push_back(pRoot->m_value);// 如果是葉節點，并且路徑上的葉節點上值之和等于輸入的值，則打印出這條路徑bool isLeaf = pRoot->m_pLeft == NULL && pRoot->m_pRight == NULL;if(currentSum == expectedSum && isLeaf){printf("The path is Find: ");std::vector<int>::iterator iter = path.begin();for(; iter < path.end(); ++iter){print("%d\t", *iter);}printf("\n");}// 如果不是葉節點就遍歷它的子節點if(pRoot->m_pLeft != NULL)FindPath(pRoot->m_pLeft,expectedSum,path,currentSum);if(pRoot->m_pRight != NULL)FindPath(pRoot->m_pRight,expectedSum,path,currentSum);// 在返回父節點的時候，在路徑上刪除當前節點，并在 currentSum 中減去當前的值currentSum -= pRoot->m_value;path.pop_back(); } /* 8、求樹中兩個結點的最低公共祖先。注：由于這里涉及到樹的類型，不同的類型有不同的解法，這里就默認是最為普通的樹。如果是二叉搜索樹，則是比較方便的。因為二叉搜索樹是排過序的，如果當前節點比輸入的兩個節點的值都大，說明兩個節點都在左子樹,反之，在右子樹。若在左邊，則下一步遍歷左子節點,若在右邊，則遍歷右子節點。依次遞歸遍歷直到找到兩個第一個在兩個節點值之間的節點，即為最低公共祖先。如果不是二叉搜索樹，是一般的樹，且二叉樹都不是，但是有指向父節點的指針。則可以將其中一條路徑轉換為從輸入節點到根節點的鏈表，此時問題就可以轉化為兩個鏈表求取第一個公共子節點的問題。如果也沒有指向父節點的指針，就是最為普通的樹。則可以采用輔助空間存儲從根節點到輸入節點的鏈表，然后在求取最后公共子節點的問題。算法如下： */ bool GetNodePath(TreeNode* pRoot,TreeNode* pNode,std::list<TreeNode* > & path) {if(pRoot == pNode)return true;path.push_back(pRoot);bool found = false;std::vector<TreeNode* >::iterator i = pRoot->m_vChildrne.begin();while(!found && i<pRoot->m_vChildrne.end()){found = GetNodePath(*i,pNode,path);++i;}if(!found)path.pop_back();return found; }TreeNode* getLastCommonNode(const std::list<TreeNode* > &path1,const std::list<TreeNode* > & path2) {std::list<TreeNode* >::const_iterator iter1 = path1.begin();std::list<TreeNode* >::const_iterator iter2 = path2.begin();TreeNode* pLastNode = NULL;while(iter1 != path1.end() && iter2 != path2.end()){if(*iter1 == *iter2)pLastNode = *iter1;++ iter1;++ iter2;}return pLastNode; }TreeNode* getLastCommonParent(TreeNode* pRoot,TreeNode* pNode1,TreeNode* pNode2) {if(pRoot == NULL || pNode1 == NULL || pNode2 == NULL)return NULL;std::list<TreeNode* > path1;GetNodePath(pRoot,pNode1,path1);std::list<TreeNode* > path2;GetNodePath(pRoot,pNode2,path2);return GetLastCommonNode(path1,path2); }/* 9、求最小的 K 個數，若果不能改變數組順序，建議直接使用堆結構（適合處理海量數據）。如 stl 里面的優先級隊列 priority_queue,或者使用紅黑樹結構的 set、map 等。這里使用 set */ typedef std::multiset<int, std::greater<int> > intSet; typedef std::multiset<int, std::greater<int> >::iterator setIterator;void GetLeastNumber(const std::vector<int> & data,intSet & leastNumbers,int k) {leastNumbers.clear();if(k<1 || k > data.size())return;vector<int>::const_iterator iter = data.begin();for(; iter != data.end(); ++iter){// 先插入 k 個值if((leastNumbers.size()) < k)leastNumbers.intsert(*iter);else { // 然后在調整setIterator iterGreastest = leastNumbers.begin();if(*iter < *(leastNumbers.begin())){leastNumbers.erase(iterGreastest);leastNumbers.insert(*iter);}}} }

總結

以上是生活随笔為你收集整理的面试基础算法及编程 第三弹（树（二叉树）相关：主要考察指针相关的操作）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。