二叉樹經(jīng)典面試題-創(chuàng)新互聯(lián)
首先給出五道關(guān)于二叉樹的面試題，題目很簡(jiǎn)單，這里會(huì)給出簡(jiǎn)單分析，具體代碼，這里只給出最優(yōu)解法。
◆找出二叉樹中最遠(yuǎn)結(jié)點(diǎn)的距離
◆由前序遍歷和中序遍歷重建二叉樹
◆判斷一棵二叉樹是否為完全二叉樹
◆求二叉樹中兩個(gè)結(jié)點(diǎn)的最近公共祖先
◆將二叉搜索樹轉(zhuǎn)換成一個(gè)排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點(diǎn)，只能調(diào)整樹中結(jié)點(diǎn)指針的指向。
找出二叉樹中最遠(yuǎn)結(jié)點(diǎn)的距離
首先需要考慮一下，二叉樹中什么距離是最遠(yuǎn)距離。以根節(jié)點(diǎn)為軸，左右子樹的大深度？當(dāng)然這只是一部分。準(zhǔn)確地說，大深度是以根節(jié)點(diǎn)為軸，左右子樹的大深度之和與以各個(gè)子樹的根節(jié)點(diǎn)為軸左右子樹的大深度之和的較大值。
雖然有點(diǎn)繞，看下圖就會(huì)明白。
思路一：解決這個(gè)問題最直接的方式就是遍歷。對(duì)每個(gè)結(jié)點(diǎn)求深度，之后再與保存的大深度max_depth進(jìn)行對(duì)比，但對(duì)于O(n^2)的時(shí)間復(fù)雜度，我們還是選擇能避免就避免，這應(yīng)該是一種比較糟糕的時(shí)間復(fù)雜度。
思路二：針對(duì)思路一，可以發(fā)現(xiàn)，我們重復(fù)了大量的遍歷工作。對(duì)每一個(gè)結(jié)點(diǎn)求深度，對(duì)最深的一個(gè)結(jié)點(diǎn)遍歷了n^2次，沒有線索化過的二叉樹遍歷，最常用的是遞歸方法，因此，我們可以僅僅通過一次遞歸，同時(shí)得到該結(jié)點(diǎn)的深度和以該節(jié)點(diǎn)為根的子樹的大距離。當(dāng)然，由于深度是相對(duì)整個(gè)遍歷過程的，因此在遞歸過程中，它應(yīng)該是以引用的方式進(jìn)行傳遞，我們這里不需要將深度也作為一個(gè)參數(shù)進(jìn)行傳遞，原因很簡(jiǎn)單，深度完全可以在遞歸的時(shí)候用返回值接收，這也解決了對(duì)左右子樹深度的比較選取的過程中多余創(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;
}代碼看上去很簡(jiǎn)單，這里巧妙之處在于在MaxDistance()函數(shù)中，我們沒有用它調(diào)用的_MaxDistance()函數(shù)的返回值，該函數(shù)返回值的作用，僅僅是為了提供遞歸返回使用。我們需要的max_distance是通過傳遞引用的方式獲取的。
由前序遍歷和中序遍歷重建二叉樹
這道題應(yīng)該是網(wǎng)上做爛的題目，這里只是重新提一下，因?yàn)樗]有什么建檔方法可言。
我們需要考慮，前、中、后序遍歷三種方式遍歷結(jié)果有什么特點(diǎn)。
前序遍歷：第一個(gè)元素必然是根節(jié)點(diǎn)，擴(kuò)展一點(diǎn)將，如果我們從前序遍歷的序列中取出的一段屬于某個(gè)子樹的前序遍歷段，那么該子序列的第一個(gè)結(jié)點(diǎn)也將是該子樹的根節(jié)點(diǎn)。
中序遍歷：中序遍歷由于是先左后根，最后再右的順序，因此，當(dāng)我們知道某個(gè)結(jié)點(diǎn)為跟結(jié)點(diǎn)的話，那么它的左右兩側(cè)分別是左子樹和右子樹的中序遍歷序列。同上，也擴(kuò)展一點(diǎn)將，只要可以找到某一段子樹中序遍歷序列的根節(jié)點(diǎn)，那么該序列中，跟結(jié)點(diǎn)的左右兩側(cè)序列也是該子樹的左右子樹。
后續(xù)遍歷：后續(xù)遍歷的特點(diǎn)是遍歷完左右結(jié)點(diǎn)之后再遍歷跟結(jié)點(diǎn)。和前序遍歷的區(qū)別就在于把根節(jié)點(diǎn)放到了最后訪問，因此，兩種遍歷的結(jié)果類似，只不過需要從后向前依次取元素。也就是說，最后一個(gè)元素，是當(dāng)前樹的根節(jié)點(diǎn)。
經(jīng)過上面的分析，我們可以得出一個(gè)這樣的結(jié)論，如果我們想重建二叉樹，我們至少需要兩種遍歷的序列，而且必須要有中序遍歷序列。
接下來我們討論如何利用前序和中序遍歷的結(jié)果重建二叉樹。大致可分為以下四步：
1. 用前序序列的第一個(gè)結(jié)點(diǎn)作為根結(jié)點(diǎn);
2. 在中序序列中查找根結(jié)點(diǎn)的位置，并以此為界將中序序列劃分為左、右兩個(gè)序列(左、右子樹);
3. 根據(jù)左、右子樹的中序序列中的結(jié)點(diǎn)個(gè)數(shù)，將前序序列去掉根結(jié)點(diǎn)后的序列劃分為左、右兩個(gè)序列，它們分別是左、右子樹的前序序列;
4. 對(duì)左、右子樹的前序序列和中序序列遞歸地實(shí)施同樣方法，直到所得左、右子樹為空。
下來看實(shí)現(xiàn)代碼。
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);
}仔細(xì)觀察可以發(fā)現(xiàn)，這里使用的容器是string，我這里選用string作為容器，是因?yàn)閟tring有自帶的查找某個(gè)元素的功能，同時(shí)可以實(shí)現(xiàn)部分截取，方便構(gòu)建子序列，缺點(diǎn)就是每個(gè)結(jié)點(diǎn)中key的類型只能是字符。當(dāng)然，這里也可以選用vector等其他容器，只不過vector沒有內(nèi)置的Find函數(shù)，因此在中序遍歷序列中找根節(jié)點(diǎn)的時(shí)候需要進(jìn)行遍歷，vector構(gòu)建子序列時(shí)也并不復(fù)雜，可以通過迭代器區(qū)間直接構(gòu)造一個(gè)vector對(duì)象。這里點(diǎn)到為止。
判斷一棵二叉樹是否為完全二叉樹
首先需要知道的是什么是滿二叉樹。若設(shè)二叉樹的深度為h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到大個(gè)數(shù)，第 h 層所有的結(jié)點(diǎn)都連續(xù)集中在最左邊，這就是完全二叉樹。
判斷一棵樹是不是滿二叉樹，就不能再像之前那樣，遞歸去遍歷，因?yàn)檫f歸是在走深度，所以解決這一問題，需要借助queue完成層序遍歷。
我們簡(jiǎn)單的層序遍歷是先將根節(jié)點(diǎn)入隊(duì)列，之后依次訪問隊(duì)列的front結(jié)點(diǎn)，訪問完成，將front結(jié)點(diǎn)pop，同時(shí)將左右不為空的子節(jié)點(diǎn)入隊(duì)列，直到隊(duì)列為空。這一點(diǎn)應(yīng)該沒有太大問題?；叵胍幌拢覀?cè)诤?jiǎn)單層序遍歷的時(shí)候，注意了什么問題？如果子結(jié)點(diǎn)為NULL，則不入隊(duì)列，防止下次對(duì)空結(jié)點(diǎn)進(jìn)行訪問 。
回到我們一開始的問題，判斷一棵二叉樹是否為滿二叉樹。這里在簡(jiǎn)單層序遍歷上做一些處理，先不考慮隊(duì)列的問題，當(dāng)我們簡(jiǎn)單地在走層序遍歷過程中，當(dāng)碰到一個(gè)結(jié)點(diǎn)為NULL時(shí)，如果之后都是空結(jié)點(diǎn)，那么該二叉樹為完全二叉樹，否則，不滿足完全二叉樹。
因此，要實(shí)現(xiàn)這個(gè)邏輯，就不能只是簡(jiǎn)單地把非空結(jié)點(diǎn)入隊(duì)列，所有結(jié)點(diǎn)都需要入隊(duì)列，當(dāng)front變?yōu)镹ULL時(shí)，表示讀取到了一個(gè)空結(jié)點(diǎn)，此時(shí)，它的子節(jié)點(diǎn)之前的所有結(jié)點(diǎn)都已經(jīng)入隊(duì)列，當(dāng)隊(duì)列中還存在空結(jié)點(diǎn)，則該樹不滿足滿二叉樹。
代碼實(shí)現(xiàn)如下：
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;
}求二叉樹中兩個(gè)結(jié)點(diǎn)的最近公共祖先
第一次看到這道題，感覺無從下手，后來仔細(xì)想想，不是廢話么，只告訴了要找最近公共祖先，二叉樹的特點(diǎn)都不知道，怎么找......沒辦法，分情況看。
情況一：搜索二叉樹
這應(yīng)該是最簡(jiǎn)單的情況了，搜索二叉樹始終滿足根結(jié)點(diǎn)大于左孩子，小于右孩子。那他們的公共祖先的key值就必然介于兩個(gè)結(jié)點(diǎn)之間。即
(root->_data >= node1->_data && root->_data <= node2->_data) ||(root->_data >= node2->_data && root->_data <= node1->_data)
因此，這樣一來就簡(jiǎn)單了很多，代碼實(shí)現(xiàn)如下：
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的出現(xiàn)的。因?yàn)檫@種做法有個(gè)缺陷，如果兩個(gè)結(jié)點(diǎn)不再樹中呢？但是再想一想，我傳遞的參數(shù)是 Node* ，該結(jié)點(diǎn)一定是通過Find()函數(shù)或其他可以返回Node* 類型的函數(shù)返回的，如果不存在某個(gè)結(jié)點(diǎn)，這里參數(shù)傳遞一定是NULL，因此這里添加了if判斷。
情況二：帶父指針的二叉樹
如果說一個(gè)該二叉樹結(jié)構(gòu)中有父指針，那么這道題處理起來就應(yīng)該容易的多。有父指針，意味著我可以從下向上去遍歷，沿著父節(jié)點(diǎn)的路徑直到走到根節(jié)點(diǎn)。那問題就轉(zhuǎn)化為求兩個(gè)單鏈表的交點(diǎn)CrossNode。
求解單鏈表的交點(diǎn)解法有兩種，一就是對(duì)兩個(gè)單鏈表進(jìn)行遍歷并求出長(zhǎng)度，然后再重新遍歷，第二次遍歷時(shí)，較長(zhǎng)的單鏈表的指針要先走長(zhǎng)度差次，當(dāng)兩個(gè)指針相同時(shí)，表明相遇，如果走到NULL，則只有一種情況，這兩個(gè)結(jié)點(diǎn)不在一棵樹內(nèi)。第二種方法就是構(gòu)建環(huán)。讓根節(jié)點(diǎn)的父指針parent指向其中一個(gè)結(jié)點(diǎn)，以另一個(gè)結(jié)點(diǎn)為頭，判斷鏈表是否帶環(huán)。
這里給出通過找交點(diǎn)找到最近公共結(jié)點(diǎn)的代碼：
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é)點(diǎn)的二叉樹
這種情況應(yīng)該是最復(fù)雜的。
這里給出一種新思路，應(yīng)該很少用過的。在C++里面，有個(gè)結(jié)構(gòu)體叫pair，是庫里封裝好的，提供了兩個(gè)成員，通過這種方式，我們可以一次返回多個(gè)值。給出pair的定義。
template<classT1,classT2>structpair
{typedefT1 first_type;typedefT2 second_type;
T1 first;
T2 second;
pair() : first(T1()), second(T2()) {}
}給這個(gè)東西有什么用呢？
繼續(xù)回到我們一開始的問題。我們要找兩個(gè)結(jié)點(diǎn)的最近父節(jié)點(diǎn)。當(dāng)然一層嵌套一層地遍歷二叉樹也有可能得出結(jié)果，但效率太低，至少是O(n^2)的時(shí)間復(fù)雜度。我們得到什么信息的時(shí)候，可以確定一個(gè)結(jié)點(diǎn)是他們的公共祖先？如果我們可以得到信息，在該結(jié)點(diǎn)的左右子樹中找到了兩個(gè)結(jié)點(diǎn)，那這個(gè)結(jié)點(diǎn)一定是他們的父節(jié)點(diǎn)（先不考慮是否為最近）。
換句話說，我們需要在一個(gè)結(jié)點(diǎn)出得到的信息，應(yīng)該是在它的左右子樹中遍歷到的兩個(gè)結(jié)點(diǎn)的個(gè)數(shù)。同時(shí)因?yàn)橐捎玫氖沁f歸遍歷，因此我們需要返回該結(jié)點(diǎn)。怎么解決“最近”的問題呢？遞歸給我們提供了方便，只要在一開始進(jìn)行一次判斷即可。
代碼實(shí)現(xiàn)如下：
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結(jié)構(gòu)題中保存的兩個(gè)對(duì)象，第一個(gè)是當(dāng)前結(jié)點(diǎn)，另外一個(gè)是在它左右子樹中找到的兩個(gè)結(jié)點(diǎn)個(gè)數(shù)，當(dāng)然包括了它自己。一旦當(dāng)某次發(fā)現(xiàn)，該結(jié)點(diǎn)的second為2時(shí)，表明該結(jié)點(diǎn)就是我們要找的最近父結(jié)點(diǎn)。這里采用的依舊是后續(xù)遍歷的方式。
將二叉搜索樹轉(zhuǎn)換成一個(gè)排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點(diǎn)，只能調(diào)整樹中結(jié)點(diǎn)指針的指向。
這道題應(yīng)該和二叉樹的線索化類似，不過有一點(diǎn)不同的是，線索化只是針對(duì)空結(jié)點(diǎn)而言的，只有當(dāng)二叉樹中某個(gè)指針為空，才需要改變它的指向。
對(duì)于二叉搜索樹而言，它的中序遍歷序列就是有序的，因此，這里依舊采用的是中序遍歷來改變它。將二叉樹轉(zhuǎn)換為雙向鏈表，其實(shí)就是讓左孩子指針指向該結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)，右孩子指針指向下一個(gè)結(jié)點(diǎn)。因此遍歷的時(shí)候，需要兩個(gè)指針，prev和cur。
還有一點(diǎn)需要注意，轉(zhuǎn)換為雙向鏈表之后，二叉樹的結(jié)構(gòu)即不復(fù)存在，我們就不能再通過根節(jié)點(diǎn)去遍歷二叉樹，因此這里在將二叉樹轉(zhuǎn)換為雙向鏈表之前，首先要做的是保存它的最左結(jié)點(diǎn)，因?yàn)樗淖钭蠼Y(jié)點(diǎn)是雙向鏈表的頭結(jié)點(diǎn)。
代碼實(shí)現(xiàn)如下：
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);
}這就是這五道面試題，解題思路和代碼已經(jīng)給出。可以發(fā)現(xiàn)，遞歸是降低二叉樹時(shí)間復(fù)雜度的有效方式，時(shí)間復(fù)雜度一般可以用O(n^2)降低到O(n)，缺點(diǎn)就是帶來了O(logN)的空間復(fù)雜度，logN是非常小的復(fù)雜度，相對(duì)來說，遞歸解決二叉樹在絕大多數(shù)情況下，是一種相對(duì)較為優(yōu)的解法。
同時(shí)，這里加入了一種新的思想，就是pair，如何給pair的兩個(gè)成員分配合理的類型和功能，這個(gè)是需要考慮的問題，但不得不說，有些情況下，pair可以帶來意想不到的效果。
另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。
標(biāo)題名稱：二叉樹經(jīng)典面試題-創(chuàng)新互聯(lián)
文章轉(zhuǎn)載：http://aaarwkj.com/article10/dohhdo.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供Google、面包屑導(dǎo)航、微信小程序、域名注冊(cè)、App開發(fā)、軟件開發(fā)
聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)
- 中小企業(yè)如何選擇虛擬主機(jī)建站 2016-08-20
- 網(wǎng)絡(luò)服務(wù)器、云虛擬主機(jī)對(duì)seo優(yōu)化的影響 2014-07-23
- 選購虛擬主機(jī)要考慮到的一些因素 2021-06-26
- 服務(wù)器之家淺談虛擬主機(jī)與云服務(wù)器的區(qū)別在哪里？ 2022-10-11
- 什么是虛擬主機(jī)空間進(jìn)程工作數(shù)？ 2021-02-08
- 徐匯做網(wǎng)站告訴你如何判斷虛擬主機(jī)的好壞 2022-09-24
- 云服務(wù)器與虛擬主機(jī)到底有何不同？ 2017-04-12
- 香港虛擬主機(jī)為企業(yè)帶來哪些好處 2021-02-06
- 云虛擬主機(jī)價(jià)格是多少？ 2022-05-02
- 虛擬主機(jī)、vps、云主機(jī)、獨(dú)立服務(wù)器、站群服務(wù)器 2021-02-20
- 選購網(wǎng)站虛擬主機(jī)（空間）需要注意的一些方面 2022-06-17
- 虛擬主機(jī)和vps哪種更適合？ 2022-07-06