0 概述
繼上一篇總結了二叉樹的基礎操作後,這一篇文章彙總下常見的二叉樹相關面試題,主要分為判斷類、構建類、存儲類、查找類、距離類、混合類這六類大問題。
本文所有代碼
https://github.com/shishujuan/dsalg/tree/master/code/ds/tree/binary_tree
1 判斷類問題
判斷類問題主要分下下判斷二叉樹是否是二叉搜索樹、二叉完全樹,以及兩棵二叉樹是否同構這三個問題。
1.1 判斷一棵二叉樹是否是二叉搜索樹(BST)
題:給定一棵二叉樹,判斷該二叉樹是否是二叉搜索樹。
二叉搜索樹是一種二叉樹,但是它有附加的一些約束條件,這些約束條件必須對每個結點都成立:
- 結點的左子樹所有結點的值都小於等於該結點的值。
- 結點的右子樹所有結點的值都大於該結點的值。
- 結點的左右子樹同樣都必須是二叉搜索樹。
一種錯誤解法
初看這個問題,容易這麼實現:假定當前結點值為 k,對於二叉樹中每個結點,判斷其左孩子的值是否小於 k,其右孩子的值是否大於 k。如果所有結點都滿足該條件,則該二叉樹是一棵二叉搜索樹。
實現代碼如下:
<code>int isBSTError(BTNode *root){ if (!root) return 1; if (root->left && root->left->value >= root->value) return 0; if (root->right && root->right->value value) return 0; if (!isBSTError(root->left) || !isBSTError(root->right)) return 0; return 1; }/<code>
很不幸,這種做法是錯誤的,如下面這棵二叉樹滿足上面的條件,但是它並不是二叉搜索樹。
<code> 10 / \\ 5 15 -------- binary tree(1) 符合上述條件的二叉樹,但是並不是二叉搜索樹。 / \\ 6 20/<code>
解1:蠻力法
上面的錯誤解法是因為判斷不完整導致,可以這樣來判斷:
- 判斷結點左子樹最大值是否大於等於結點的值,如果是,則該二叉樹不是二叉搜索樹,否則繼續下一步判斷…
- 判斷右子樹最小值是否小於或等於結點的值,如果是,則不是二叉搜索樹,否則繼續下一步判斷。
- 遞歸判斷左右子樹是否是二叉搜索樹。(代碼中的 bstMax 和 bstMin 函數功能分別是返回二叉樹中的最大值和最小值結點,這裡假定二叉樹為二叉搜索樹,實際返回的不一定是最大值和最小值結點)
<code>int isBSTUnefficient(BTNode *root){ if (!root) return 1; if (root->left && bstMax(root->left)->value >= root->value) return 0; if (root->right && bstMin(root->right)->value value) return 0; if (!isBSTUnefficient(root->left) || !isBSTUnefficient(root->right)) return 0; return 1;}/<code>
解2:一次遍歷法
以前面提到的 binary tree(1) 為例,當我們遍歷到結點 15 時,我們知道右子樹結點值肯定都 >=10。當我們遍歷到結點 15 的左孩子結點 6 時,我們知道結點 15 的左子樹結點值都必須在 10 到 15 之間。顯然,結點 6 不符合條件,因此它不是一棵二叉搜索樹。
<code>int isBSTEfficient(BTNode* root, BTNode *left, BTNode *right){ if (!root) return 1; if (left && root->value <= left->value) return 0; if (right && root->value > right->value) return 0; return isBSTEfficient(root->left, left, root) && isBSTEfficient(root->right, root, right);}/<code>
解3:中序遍歷解法
還可以模擬樹的中序遍歷來判斷BST,可以直接將中序遍歷的結果存到一個輔助數組,然後判斷數組是否有序即可判斷是否是BST。當然,我們可以不用輔助數組,在遍歷時通過保留前一個指針 prev,據此來實現判斷BST的解法,初始時 prev = NULL。
<code>int isBSTInOrder(BTNode *root, BTNode *prev){ if (!root) return 1; if (!isBSTInOrder(root->left, prev)) return 0; if (prev && root->value value) return 0; return isBSTInOrder(root->right, root);}/<code>
1.2 判斷二叉樹是否是完全二叉樹
題:給定一棵二叉樹,判斷該二叉樹是否是完全二叉樹(完全二叉樹定義:若設二叉樹的深度為 h,除第 h 層外,其它各層 (1~h-1) 的結點數都達到最大個數,第 h 層所有的結點都連續集中在最左邊,這就是完全二叉樹)。
解1:常規解法-中序遍歷
先定義一個 滿結點 的概念:即一個結點存在左右孩子結點,則該結點為滿結點。在代碼中定義變量 flag 來標識是否發現非滿結點,為1表示該二叉樹存在非滿結點。完全二叉樹如果存在非滿結點,則根據層序遍歷隊列中剩下結點必須是葉子結點,且如果一個結點的左孩子為空,則右孩子結點也必須為空。
<code>int isCompleteBTLevelOrder(BTNode *root){ if (!root) return 1; BTNodeQueue *queue = queueNew(btSize(root)); enqueue(queue, root); int flag = 0; while (QUEUE_SIZE(queue) > 0) { BTNode *node = dequeue(queue); if (node->left) { if (flag) return 0; enqueue(queue, node->left); } else { flag = 1; } if (node->right) { if (flag) return 0; enqueue(queue, node->right); } else { flag = 1; } } return 1;}/<code>
解2:更簡單的方法-判斷結點序號法
更簡單的方法是判斷結點序號法,因為完全二叉樹的結點序號都是有規律的,如結點 i 的左右子結點序號為 2i+1 和 2i+2,如根結點序號是 0,它的左右子結點序號是 1 和 2(如果都存在的話)。
我們可以計算二叉樹的結點數目,然後依次判斷所有結點的序號,如果不是完全二叉樹,那肯定會存在結點它的序號大於等於結點數目的。如前面提到的 binary tree(1) 就不是完全二叉樹。
<code> 10(0) / \\ 5(1) 15(2) - 結點數目為5,如果是完全二叉樹結點最大的序號應該是4,而它的是6,所以不是。 / \\ 6(5) 20(6)/<code>
實現代碼如下:
<code>int isCompleteBTIndexMethod(BTNode *root, int index, int nodeCount){ if (!root) return 1; if (index >= nodeCount) return 0; return (isCompleteBTIndexMethod(root->left, 2*index+1, nodeCount) && isCompleteBTIndexMethod(root->right, 2*index+2, nodeCount));}/<code>
1.3 判斷平衡二叉樹
題:判斷一棵二叉樹是否是平衡二叉樹。所謂平衡二叉樹,指的是其任意結點的左右子樹高度之差不大於1。
<code> __2__ / \\ 1 4 ---- 平衡二叉樹示例 \\ / \\ 3 5 6/<code>
解1:自頂向下方法
判斷一棵二叉樹是否是平衡的,對每個結點計算左右子樹高度差是否大於1即可,時間複雜度為O(N^2) 。
<code>int isBalanceBTTop2Down(BTNode *root){ if (!root) return 1; int leftHeight = btHeight(root->left); int rightHeight = btHeight(root->right); int hDiff = abs(leftHeight - rightHeight); if (hDiff > 1) return 0; return isBalanceBTTop2Down(root->left) && isBalanceBTTop2Down(root->right);}/<code>
解2:自底向上方法
因為解1會重複的遍歷很多結點,為此我們可以採用類似後序遍歷的方式,自底向上來判斷左右子樹的高度差,這樣時間複雜度為 O(N)。
<code>int isBalanceBTDown2Top(BTNode *root, int *height){ if (!root) { *height = 0; return 1; } int leftHeight, rightHeight; if (isBalanceBTDown2Top(root->left, &leftHeight) && isBalanceBTDown2Top(root->right, &rightHeight)) { int diff = abs(leftHeight - rightHeight); return diff > 1 ? 0 : 1; } return 0;}/<code>
1.4 判斷兩棵二叉樹是否同構
題:給定兩棵二叉樹,根結點分別為 t1 和 t2,判定這兩棵二叉樹是否同構。所謂二叉樹同構就是指它們的結構相同,如下二叉樹 (1) 和 (2) 是同構的,而它們和 (3) 是不同結構的:
<code> 5 9 6 / \\ / \\ / \\ 1 2 7 12 5 9 / \\ / \\ \\4 3 5 8 10 二叉樹(1) 二叉樹(2) 二叉樹(3)/<code>
解:二叉樹結構是否相同,還是遞歸實現,先判斷根結點是否同構,然後再判斷左右子樹。
<code>int isOmorphism(BTNode *t1, BTNode *t2){ if (!t1 || !t2) return (!t1) && (!t2); return isOmorphism(t1->left, t2->left) && isOmorphism(t1->right, t2->right);}/<code>
2 構建類問題
構建類問題主要是使用二叉樹的兩種遍歷順序來確定二叉樹的另外一種遍歷順序問題。在上一篇文章中我們分析過二叉樹的先序、中序、後序遍歷的遞歸和非遞歸實現。
那麼,是否可以根據先序、中序或者先序、後序或者中序、後序唯一確定一棵二叉樹呢?
答案是 在沒有重複值的二叉樹中, 根據先序遍歷和後序遍歷無法唯一確定一棵二叉樹,而根據先序、中序或者中序、後序遍歷是可以唯一確定一棵二叉樹的。
1)先序和後序遍歷無法唯一確定一棵二叉樹
一個簡單的例子如下,這兩棵二叉樹的先序遍歷和後序遍歷相同,由此可以證明先序遍歷和後序遍歷無法唯一確定一棵二叉樹。
<code> 1 1/ /2 2\\ /3 3先序遍歷:1 2 3後序遍歷:3 2 1/<code>
2)先序和中序遍歷可以唯一確定二叉樹
簡單證明:因為先序遍歷的第一個元素是根結點,該元素將二叉樹中序遍歷序列分成兩部分,左邊(假設有L個元素)表示左子樹,若左邊無元素,則說明左子樹為空;右邊(假設有R個元素)是右子樹,若為空,則右子樹為空。
根據前序遍歷中"根-左子樹-右子樹"的順序,則由從先序序列的第二元素開始的L個結點序列和中序序列根左邊的L個結點序列構造左子樹,由先序序列最後R個元素序列與中序序列根右邊的R個元素序列構造右子樹。
3)中序和後序遍歷可以唯一確定二叉樹
簡單證明: 假定二叉樹結點數為 n,假定中序遍歷為 S1, S2, …, Sn,而後序遍歷為 P1, P2, …, Pn,因為後序遍歷最後一個結點 Pn 是根結點,則可以根據 Pn 將中序遍歷分為兩部分,則其中左邊L個結點是左子樹結點,右邊R個結點是右子樹結點,則後序遍歷中的 1~L 個結點是左子樹的後序遍歷,由此 PL 是左子樹的根,與前面同理可以將中序遍歷分成兩部分,直到最終確定該二叉樹。
2.1 根據先序、中序遍歷構建二叉樹
題:給定一棵二叉樹的先序和中序遍歷序列,請構建該二叉樹(注:二叉樹沒有重複的值)。
<code>先序遍歷:7 10 4 3 1 2 8 11中序遍歷:4 10 3 1 7 11 8 2二叉樹如下: 7 / \\ 10 2 / \\ / 4 3 8 \\ / 1 11/<code>
解:根據前面的分析來解這個問題。
- 先序遍歷的第一個結點總是根結點。如上圖中的二叉樹,根結點為 7 。
- 可以觀察到在中序遍歷中,根結點7是第 4 個值(從0開始算起)。由於中序遍歷順序為:左子樹,根結點,右子樹。所以根結點7左邊的 {4,10,3,1} 這四個結點屬於左子樹,而根結點7右邊的 {11,8,2} 屬於右子樹。
- 據此可以寫出遞歸式了。注意關於如何得到根結點在中序遍歷中的位置代碼中使用線性掃描查找位置,每次查找需要 O(N) 的時間,整個算法需要 O(N^2) 的時間。如果要提高效率,也可以哈希表來存儲與查找根結點在中序遍歷中的位置,每次查找只需要 O(1) 的時間,這樣構建整棵樹只需要 O(N)的時間。
- 調用方法為 buildBTFromPreInOrder(preorder, inorder, n, 0, n);,其中 preorder 和 inorder 分別為先序中序遍歷數組,n 為數組大小。
<code>/*** 輔助函數,查找根結點在中序遍歷中的位置。*/int findBTRootIndex(int inorder[], int count, int rootVal){ int i; for (i = 0; i left = buildBTFromPreInOrder(preorder+1, inorder, leftCount, offset, count); root->right = buildBTFromPreInOrder(preorder+leftCount+1, inorder, rightCount, offset+leftCount+1, count); return root;}/<code>
2.2 根據中序、後序遍歷構建二叉樹
題:給定一棵二叉樹的中序和後序遍歷序列,請構建該二叉樹(注:二叉樹沒有重複的值)。
<code>中序遍歷:4 10 3 1 7 11 8 2後序遍歷:4 1 3 10 11 8 2 7二叉樹如下: 7 / \\ 10 2 / \\ / 4 3 8 \\ / 1 11/<code>
解:跟前面一題類似,只是這裡根結點是從後序遍歷數組的最後一個元素取。
<code>/*** 根據中序和後序遍歷構建二叉樹*/BTNode *buildBTFromInPostOrder(int postorder[], int inorder[], int n, int offset, int count){ if (n == 0) return NULL; int rootVal = postorder[n-1]; int rootIndex = findBTRootIndex(inorder, count, rootVal); int leftCount = rootIndex - offset; // 左子樹結點數目 int rightCount = n - leftCount - 1; // 右子樹結點數目 BTNode *root = btNewNode(rootVal); root->left = buildBTFromInPostOrder(postorder, inorder, leftCount, offset, count); root->right = buildBTFromInPostOrder(postorder+leftCount, inorder, rightCount, offset+leftCount+1, count); return root;}/<code>
3 存儲類問題
3.1 二叉搜索樹存儲和恢復
題:設計一個算法,將一棵二叉搜索樹(BST)保存到文件中,需要能夠從文件中恢復原來的二叉搜索樹,注意算法的時空複雜度。
<code> 30 / \\ 20 40 / / \\ 10 35 50/<code>
思路
二叉樹遍歷算法有先序遍歷、中序遍歷、後序遍歷算法等。但是它們中間哪一種能夠用於保存BST到文件中並從文件中恢復原來的BST,這是個要考慮的問題。
假定用中序遍歷,因為這棵BST的中序遍歷為 10 20 30 35 40 50,可能的結構是下面這樣,因此 中序遍歷不符合要求 。
<code> 50 / 40 / 35 / 30 / 20 /10/<code>
既然中序遍歷不行,後序遍歷如何?後序遍歷該BST可以得到:10 20 35 50 40 30 。讀取這些結點並構造出原來的BST是個難題,因為在構造二叉樹時是先構造父結點再插入孩子結點,而後序遍歷序列是先讀取到孩子結點然後才是父結點,所以 後續遍歷也不符合條件 。
綜合看來,只有先序遍歷滿足條件 。該BST的先序遍歷是 30 20 10 40 35 50 。我們觀察到重要的一點就是:一個結點的父親結點總是在該結點之前輸出 。有了這個觀察,我們從文件中讀取BST結點序列後,總是可以在構造孩子結點之前構造它們的父結點。將BST寫入到文件的代碼跟先序遍歷一樣。
那麼讀取恢復怎麼做呢?使用二叉搜索樹 bstInsert() 方法執行 N 次插入操作即可,如果二叉搜索樹平衡的話每次插入需要時間 O(lgN),共需要 O(NlgN) 的時間,而最壞情況下為 O(N^2)。
<code>/** * 存儲二叉樹到文件中-使用先序遍歷 */void bstSave(BTNode *root, FILE *fp){ if (!root) return; char temp[30]; sprintf(temp, "%d\\n", root->value); fputs(temp, fp); bstSave(root->left, fp); bstSave(root->right, fp);}/** * 從文件中恢復二叉樹 */BTNode *bstRestore(FILE *fp){ BTNode *root = NULL; char *s; char buf[30]; while ((s = fgets(buf, 30, fp))) { int nodeValue = atoi(s); root = bstInsert(root, nodeValue); } return root;}/<code>
3.2 二叉樹存儲和恢復
題:設計一個算法能夠實現二叉樹(注意,不是二叉搜索樹BST)存儲和恢復。
解:3.1節提到過使用先序遍歷可以保存和恢復二叉搜索樹,而這個題目是針對二叉樹,並不是BST,所以不能用前面的方式。不過,我們可以採用先序遍歷的思想,只是在這裡需要改動。為了能夠在重構二叉樹時結點能夠插入到正確的位置,在使用先序遍歷保存二叉樹到文件中的時候需要把 NULL 結點也保存起來(可以使用特殊符號如 # 來標識 NULL 結點)。
注意:本題採用 # 保存 NULL 結點的方法存在缺陷,如本方法中二叉樹結點值就不能是 #。如果要能保存各種字符,則需要採用其他方法來實現了。
<code> 30 / \\ 10 20 / / \\50 45 35/<code>
如上面這棵二叉樹,保存到文件中則為 30 10 50 # # # 20 45 # # 35 # #。於是,保存和恢復實現的代碼如下:
<code>/** * 存儲二叉樹到文件中 */void btSave(BTNode *root, FILE *fp){ if (!root) { fputs("#\\n", fp); } else { char temp[30]; sprintf(temp, "%d\\n", root->value); fputs(temp, fp); btSave(root->left, fp); btSave(root->right, fp); }}/** * 從文件恢復二叉樹 */BTNode *btRestore(BTNode *root, FILE *fp){ char buf[30]; char *s = fgets(buf, 30, fp); if (!s || strcmp(s, "#\\n") == 0) return NULL; int nodeValue = atoi(s); root = btNewNode(nodeValue); root->left = btRestore(root->left, fp); root->right = btRestore(root->right, fp); return root;}/<code>
4 查找類問題
查找類問題主要包括:查找二叉樹/二叉搜索樹的最低公共祖先結點,或者是二叉樹中的最大的子樹且該子樹為二叉搜索樹等。
4.1 二叉搜索樹最低公共祖先結點
題:給定一棵二叉搜索樹(BST),找出樹中兩個結點的最低公共祖先結點(LCA)。如下面這棵二叉樹結點 2 和 結點 8 的 LCA 是 6,而結點 4 和 結點 2 的 LCA 是 2。
<code> ______6______ / \\ __2__ __8__ / \\ / \\ 0 4 7 9 / \\ 3 5/<code>
解:我們從頂往下遍歷二叉搜索樹時,對每個遍歷到的結點,待求LCA的兩個結點可能有如下四種分佈情況:
- 兩個結點都在樹的左子樹中:LCA一定在當前遍歷結點的左子樹中。
- 兩個結點都在樹的右子樹中:LCA一定在當前遍歷結點右子樹中。
- 一個結點在樹的左邊,一個結點在樹的右邊:LCA就是當前遍歷的結點。
- 當前結點等於這兩個結點中的一個:LCA也是當前遍歷的結點。
<code>BTNode *bstLCA(BTNode *root, BTNode *p, BTNode *q){ if (!root || !p || !q) return NULL; int maxValue = p->value >= q->value ? p->value : q->value; int minValue = p->value value ? p->value : q->value; if (maxValue value) { return bstLCA(root->left, p, q); } else if (minValue > root->value) { return bstLCA(root->right, p, q); } else { return root; }}/<code>
4.2 二叉樹(不一定是BST)最低公共祖先結點
題:給定二叉樹中的兩個結點,輸出這兩個結點的最低公共祖先結點(LCA)。注意,該二叉樹不一定是二叉搜索樹。
<code> _______3______ / \\ ___5__ ___1__ / \\ / \\ 6 2 0 8 / \\ 7 4/<code>
解1:自頂向下方法
因為不一定是BST,所以不能根據值大小來判斷,不過總體思路是一樣的:我們可以從根結點出發,判斷當前結點的左右子樹是否包含這兩個結點。
- 如果左子樹包含兩個結點,則它們的最低公共祖先結點也一定在左子樹中。
- 如果右子樹包含兩個結點,則它們的最低公共祖先結點也一定在右子樹中。
- 如果一個結點在左子樹,而另一個結點在右子樹中,則當前結點就是它們的最低公共祖先結點。
因為對每個結點都要重複判斷結點 p 和 q 的位置,總的時間複雜度為 O(N^2),為此,我們可以考慮找一個效率更高的方法。
<code>/** * 二叉樹最低公共祖先結點-自頂向下解法 O(N^2) */BTNode *btLCATop2Down(BTNode *root, BTNode *p, BTNode *q){ if (!root || !p || !q) return NULL; if (btExist(root->left, p) && btExist(root->left, q)) { return btLCATop2Down(root->left, p, q); } else if (btExist(root->right, p) && btExist(root->right, q)) { return btLCATop2Down(root->right, p, q); } else { return root; }}/** * 二叉樹結點存在性判斷 */int btExist(BTNode *root, BTNode *node){ if (!root) return 0; if (root == node) return 1; return btExist(root->left, node) || btExist(root->right, node);}/<code>
解2:自底向上方法
因為自頂向下方法有很多重複的判斷,於是有了這個自底向上的方法。自底向上遍歷結點,一旦遇到結點等於p 或者 q,則將其向上傳遞給它的父結點。
父結點會判斷它的左右子樹是否都包含其中一個結點,如果是,則父結點一定是這兩個結點 p 和 q 的 LCA。如果不是,我們向上傳遞其中的包含結點 p 或者 q 的子結點,或者 NULL(如果左右子樹都沒有結點p或q)。該方法時間複雜度為O(N)。
<code>/** * 二叉樹最低公共祖先結點-自底向上解法 O(N) */BTNode *btLCADown2Top(BTNode *root, BTNode *p, BTNode *q){ if (!root) return NULL; if (root == p || root == q) return root; BTNode *left = btLCADown2Top(root->left, p, q); BTNode *right = btLCADown2Top(root->right, p, q); if (left && right) return root; // 如果p和q位於不同的子樹 return left ? left: right; //p和q在相同的子樹,或者p和q不在子樹中}/<code>
4.3 二叉樹的最大二叉搜索子樹
題:找出二叉樹中最大的子樹,該子樹為二叉搜索樹。所謂最大的子樹就是指結點數目最多的子樹。
<code> ___10___ / \\ _5_ 15 / \\ \\ 1 8 7 ___10____ / \\ _5_ 15 -------- subtree (1) / \\ 1 8 _5_ / \\ -------- subtree (2) 1 8 /<code>
根據維基百科對 子樹 的定義,一棵二叉樹T的子樹由T的某個結點和該結點所有的後代構成。也就是說,該題目中,subtree(2) 才是正確的答案,因為 subtree(1) 不包含結點7,不滿足子樹的定義。
解1:自頂向下解法
最自然的解法是以根結點開始遍歷二叉樹所有的結點,判定以當前結點為根的子樹是否是BST,如果是,則該結點為根的BST就是最大的BST。如果不是,遞歸調用左右子樹,返回其中包含較多結點的子樹。
<code>/** * 查找二叉樹最大的二叉搜索子樹-自頂向下方法 */BTNode *largestSubBSTTop2Down(BTNode *root, int *bstSize){ if (!root) { *bstSize = 0; return NULL; } if (isBSTEfficient(root, NULL, NULL)) { //以root為根結點的樹為BST,則設置結果為root並返回。 *bstSize = btSize(root); return root; } int lmax, rmax; BTNode *leftBST = largestSubBSTTop2Down(root->left, &lmax); //找出左子樹中為BST的最大的子樹 BTNode *rightBST = largestSubBSTTop2Down(root->right, &rmax); //找出右子樹中為BST的最大的子樹 *bstSize = lmax > rmax ? lmax : rmax; //設定結點最大數目 BTNode *result = lmax > rmax ? leftBST : rightBST; return result;}/<code>
解2:自底向上解法
自頂向下的解法時間複雜度為 O(N^2),每個結點都要判斷是否滿足BST的條件,可以用從底向上方法優化。
我們在判斷上面結點為根的子樹是否是BST之前已經知道底部結點為根的子樹是否是BST,因此只要以底部結點為根的子樹不是BST,則以它上面結點為根的子樹一定不是BST。我們可以記錄子樹包含的結點數目,然後跟父結點所在的二叉樹比較,來求得最大BST子樹。
<code>/** * 查找二叉樹最大的二叉搜索子樹-自底向上方法 */BTNode *largestSubBSTDown2Top(BTNode *root, int *bstSize){ BTNode *largestBST = NULL; int min, max, maxNodes=0; findLargestSubBST(root, &min, &max, &maxNodes, &largestBST); *bstSize = maxNodes; return largestBST;}/** * 查找最大二叉搜索子樹自底向上方法主體函數 * 如果是BST,則返回BST的結點數目,否則返回-1 */int findLargestSubBST(BTNode *root, int *min, int *max, int *maxNodes, BTNode **largestSubBST){ if (!root) return 0; int isBST = 1; int leftNodes = findLargestSubBST(root->left, min, max, maxNodes, largestSubBST); int currMin = (leftNodes == 0) ? root->value : *min; if (leftNodes == -1 || (leftNodes != 0 && root->value <= *max)) isBST = 0; int rightNodes = findLargestSubBST(root->right, min, max, maxNodes, largestSubBST); int currMax = (rightNodes == 0) ? root->value : *max; if (rightNodes == -1 || (rightNodes != 0 && root->value > *min)) isBST = 0; if (!isBST) return -1; *min = currMin; *max = currMax; int totalNodes = leftNodes + rightNodes + 1; if (totalNodes > *maxNodes) { *maxNodes = totalNodes; *largestSubBST = root; } return totalNodes;}/<code>
5 距離類問題
5.1 二叉樹兩個結點之間的最短距離
題:已知二叉樹中兩個結點,求這兩個結點之間的最短距離(注:最短距離是指從一個結點到另一個結點需要經過的邊的條數)。
<code> ___1___ / \\ 2 3 / \\ / \\ 4 5 6 7 \\ 8Distance(4, 5) = 2Distance(4, 6) = 4Distance(3, 4) = 3Distance(2, 4) = 1Distance(8, 5) = 5/<code>
解:兩個結點的距離比較好辦,先求出兩個結點的最低公共祖先結點(LCA),然後計算 LCA 到兩個結點的距離之和即可,時間複雜度 O(N) 。
<code>/** * 計算二叉樹兩個結點最短距離 */int distanceOf2BTNodes(BTNode *root, BTNode *p, BTNode *q){ if (!root) return 0; BTNode *lca = btLCADown2Top(root, p, q); int d1 = btDistanceFromRoot(lca, p, 0); int d2 = btDistanceFromRoot(lca, q, 0); return d1+d2;}/** * 計算二叉樹結點node和root的距離 */int btDistanceFromRoot(BTNode *root, BTNode *node, int level){ if (!root) return -1; if (root == node) return level; int left = btDistanceFromRoot(root->left, node, level+1); if (left == -1) return btDistanceFromRoot(root->right, node, level+1); return left;}/<code>
5.2 二叉搜索樹兩個結點的最短距離
題:求一棵二叉搜索樹中的兩個結點的最短距離。
解:與前面不同的是,這是一棵BST,那麼我們可以使用二叉搜索樹的特點來簡化距離計算流程,當然直接用 5.1 的方法是完全OK的,因為它是通用的計算方法。
<code>/** * 計算BST兩個結點最短距離。 */int distanceOf2BSTNodes(BTNode *root, BTNode *p, BTNode *q){ if (!root) return 0; if (root->value > p->value && root->value > q->value) { return distanceOf2BSTNodes(root->left, p, q); } else if(root->value <= p->value && root->value <= q->value){ return distanceOf2BSTNodes(root->right, p, q); } else { return bstDistanceFromRoot(root, p) + bstDistanceFromRoot(root, q); }}/** * 計算BST結點node和root的距離 */int bstDistanceFromRoot(BTNode *root, BTNode *node){ if (root->value == node->value) return 0; else if (root->value > node->value) return 1 + bstDistanceFromRoot(root->left, node); else return 1 + bstDistanceFromRoot(root->right, node);}/<code>
5.3 二叉樹中結點的最大距離
題:寫一個程序求一棵二叉樹中相距最遠的兩個結點之間的距離。
解:《編程之美》上有這道題,這題跟前面不同,要求相距最遠的兩個結點的距離,而且並沒有指定兩個結點位置。計算一個二叉樹的最大距離有兩個情況:
- 路徑為 左子樹的最深節點 -> 根節點 -> 右子樹的最深節點。
- 路徑不穿過根節點,而是左子樹或右子樹的最大距離路徑,取其大者。
<code> ___10___ / \\ _5_ 15 ------ 第1種情況 / \\ \\ 1 8 7 10 / 5 / \\ ------ 第2種情況 1 8 / \\ 2 3/<code>
我們定義函數 maxDistanceOfBT(BTNode *root) 用於計算二叉樹相距最遠的兩個結點的距離,可以遞歸的先計算左右子樹的最遠結點距離,然後比較左子樹最遠距離、右子樹最遠距離以及左右子樹最大深度之和,從而求出整個二叉樹的相距最遠的兩個結點的距離。
<code>int btMaxDistance(BTNode *root, int *maxDepth){ if (!root) { *maxDepth = 0; return 0; } int leftMaxDepth, rightMaxDepth; int leftMaxDistance = btMaxDistance(root->left, &leftMaxDepth); int rightMaxDistance = btMaxDistance(root->right, &rightMaxDepth); *maxDepth = max(leftMaxDepth+1, rightMaxDepth+1); int maxDistance = max3(leftMaxDistance, rightMaxDistance, leftMaxDepth+rightMaxDepth); // max求兩個數最大值,max3求三個數最大值,詳見代碼 return maxDistance;}/<code>
5.4 二叉樹最大寬度
題:給定一棵二叉樹,求該二叉樹的最大寬度。二叉樹的寬度指的是每一層的結點數目。如下面這棵二叉樹,從上往下1-4層的寬度分別是 1,2,3,2,於是它的最大寬度為3。
<code> 1 / \\ 2 3 / \\ \\ 4 5 8 / \\ 6 7/<code>
解1:層序遍歷法
最容易想到的方法就是使用層序遍歷,然後計算每一層的結點數,然後得出最大結點數。該方法時間複雜度為 O(N^2)。當然如果優化為使用隊列來實現層序遍歷,可以得到 O(N) 的時間複雜度。
<code>/** * 二叉樹最大寬度 */int btMaxWidth(BTNode *root){ int h = btHeight(root); int level, width; int maxWidth = 0; for (level = 1; level <= h; level++) { width = btLevelWidth(root, level); if (width > maxWidth) maxWidth = width; } return maxWidth;}/** * 二叉樹第level層的寬度 */int btLevelWidth(BTNode *root, int level){ if (!root) return 0; if (level == 1) return 1; return btLevelWidth(root->left, level-1) + btLevelWidth(root->right, level-1);}/<code>
解2:先序遍歷法
我們可以先創建一個大小為二叉樹高度 h 的輔助數組來存儲每一層的寬度,初始化為0。通過先序遍歷的方式來遍歷二叉樹,並設置好每層的寬度。最後,從這個輔助數組中求最大值即是二叉樹最大寬度。
<code>/** * 二叉樹最大寬度-先序遍歷法 */int btMaxWidthPreOrder(BTNode *root){ int h = btHeight(root); int *count = (int *)calloc(sizeof(int), h); btLevelWidthCount(root, 0, count); int i, maxWidth = 0; for (i = 0; i maxWidth) maxWidth = count[i]; } return maxWidth;}/** * 計算二叉樹從 level 開始的每層寬度,並存儲到數組 count 中。 */void btLevelWidthCount(BTNode *root, int level, int count[]){ if (!root) return; count[level]++; btLevelWidthCount(root->left, level+1, count); btLevelWidthCount(root->right, level+1, count);}/<code>
6 混合類問題
此類問題主要考察二叉樹和鏈表/數組等結合,形式偏新穎。
6.1 根據有序數組構建平衡二叉搜索樹
題:給定一個有序數組,數組元素升序排列,試根據該數組元素構建一棵平衡二叉搜索樹(Balanced Binary Search Tree)。所謂平衡的定義,就是指二叉樹的子樹高度之差不能超過1。
<code> __3__ / \\ 1 5 ---- 平衡二叉搜索樹示例 \\ / \\ 2 4 6/<code>
解:如果要從一個有序數組中選擇一個元素作為根結點,應該選擇哪個元素呢?我們應該選擇有序數組的中間元素作為根結點。選擇了中間元素作為根結點並創建後,剩下的元素分為兩部分,可以看作是兩個數組。這樣剩下的元素在根結點左邊的作為左子樹,右邊的作為右子樹。
<code>BTNode *sortedArray2BST(int a[], int start, int end){ if (start > end) return NULL; int mid = start + (end-start)/2; BTNode *root = btNewNode(a[mid]); root->left = sortedArray2BST(a, start, mid-1); root->right = sortedArray2BST(a, mid+1, end); return root;}/<code>
6.2 有序單向鏈表構建平衡二叉搜索樹
題:給定一個有序的單向鏈表,構建一棵平衡二叉搜索樹。
解:最自然的想法是先將鏈表中的結點的值保存在數組中,然後採用 6.1 中方法實現,時間複雜度為 O(N)。我們還可以採用自底向上的方法,在這裡我們不再需要每次查找中間元素。
下面代碼依舊需要鏈表長度作為參數,計算鏈表長度時間複雜度為O(N),算法時間複雜度也為O(N),所以總的時間複雜度為O(N)。
代碼中需要注意的是每次調用 sortedList2BST 函數時,list 位置都會變化,調用完函數後 list 總是指向 mid+1 的位置 (如果滿足返回條件,則 list 位置不變)。
<code>BTNode *sortedList2BST(ListNode **pList, int start, int end){ if (start > end) return NULL; int mid = start + (end-start)/2; BTNode *left = sortedList2BST(pList, start, mid-1); BTNode *parent = btNewNode((*pList)->value); parent->left = left; *pList = (*pList)->next; parent->right = sortedList2BST(pList, mid+1, end); return parent;}/<code>
例如鏈表只有2個節點 3->5->NULL,則初始 start=0, end=1, mid=0,繼而遞歸調用 sortedList2BST(pList, start,mid-1),此時直接返回 NULL。即左孩子為NULL, 根結點為 3,而後鏈表指向 5,再調用 sortedList2BST(pList, mid+1, end),而這次調用返回結點 5,將其賦給根結點 3 的右孩子。這次調用的 mid=1,調用完成後 list 已經指向鏈表末尾。
6.3 二叉搜索樹轉換為有序循環鏈表
題:給定一棵二叉搜索樹(BST),將其轉換為雙向的有序循環鏈表。
![6大類二叉樹面試題彙總解答](http://p2.ttnews.xyz/loading.gif)
解:如圖所示,需要將 BST 的左右孩子指針替換成鏈表的 prev 和 next 指針,分別指向雙向鏈表的前一個和後一個結點。相信大多數人第一反應就是中序遍歷這棵二叉樹,同時改變樹中結點的 left 和 right 指針。這裡需要額外考慮的是如何將最後一個結點的right 指針指向第一個結點,如下圖所展示的那樣。
![6大類二叉樹面試題彙總解答](http://p2.ttnews.xyz/loading.gif)
以中序遍歷遍歷一棵二叉樹的時候,每遍歷到一個結點,我們就可以修改該結點的left指針指向前一個遍歷到的結點,因為在後續操作中我們不會再用到 left 指針;與此同時,我們還需要修改前一個遍歷結點的 right 指針,讓前一個遍歷結點的 right 指針指向當前結點。
比如我們遍歷到結點2,則我們修改結點2的 left 指針指向結點1,同時需要修改結點1的 right 指針指向結點2。需要注意一點,這裡的前一個遍歷結點不是當前結點的父結點,而是當前結點的前一個比它小的結點。
看似問題已經解決,慢著,我們其實落下了重要的兩步。1)我們沒有對頭結點head賦值。2)最後一個結點的right指針沒有指向第一個結點。
解決這兩個問題的方案非常簡單:在每次遞歸調用的時候,更新當前遍歷結點的 right 指針讓其指向頭結點 head,同時更新頭結點 head 的 left 指針讓其指向當前遍歷結點。當遞歸調用結束的時候,鏈表的頭尾結點會指向正確的位置。不要忘記只有一個結點的特殊情況,它的 left 和 right 指針都是指向自己。
<code>void bt2DoublyList(BTNode *node, BTNode **pPrev, BTNode **pHead){ if (!node) return; bt2DoublyList(node->left, pPrev, pHead); // 當前結點的left指向前一個結點pPrev node->left = *pPrev; if (*pPrev) (*pPrev)->right = node; // 前一個結點的right指向當前結點 else *pHead = node; // 如果前面沒有結點,則設置head為當前結點(當前結點為最小的結點)。 // 遞歸結束後,head的left指針指向最後一個結點,最後一個結點的右指針指向head結點。 // 注意保存當前結點的right指針,因為在後面代碼中會修改該指針。 BTNode *right = node->right; (*pHead)->left = node; node->right = (*pHead); *pPrev = node;//更新前一個結點 bt2DoublyList(right, pPrev, pHead); }/<code>
這個解法非常的精巧,因為該算法是對中序遍歷的一個改進,因此它的時間複雜度為O(N),N為結點數目。當然,相比中序遍歷,我們在每次遞歸調用過程中增加了額外的賦值操作。
Java知音,專注於Java實用文章推送,不容錯過!
來源:juejin.im/post/5bab8d59e51d450e925239d9
閱讀更多 Java知音 的文章