資料結構和演算法面試題系列—二叉樹面試題彙總

二叉樹演算法 · 發表 2018-09-28 10:55:24

摘要：繼上一篇總結了二叉樹的基礎操作後，這一篇文章彙總下常見的二叉樹相關面試題，主要分為判斷類、構建類、儲存類、查詢類、距離類、混合類這六類大問題。本文所有程式碼在這裡。 1 判斷類問題判斷類問題主要分下下判斷二叉樹是否是二叉搜尋樹、二叉完全樹，以及兩棵二叉樹是否同構這三個問題。 ...

繼上一篇總結了二叉樹的基礎操作後，這一篇文章彙總下常見的二叉樹相關面試題，主要分為判斷類、構建類、儲存類、查詢類、距離類、混合類這六類大問題。本文所有程式碼在 ofollow,noindex">這裡。

1 判斷類問題

判斷類問題主要分下下判斷二叉樹是否是二叉搜尋樹、二叉完全樹，以及兩棵二叉樹是否同構這三個問題。

1.1 判斷一棵二叉樹是否是二叉搜尋樹(BST)

題：給定一棵二叉樹，判斷該二叉樹是否是二叉搜尋樹。

二叉搜尋樹是一種二叉樹，但是它有附加的一些約束條件，這些約束條件必須對每個結點都成立：

結點的左子樹所有結點的值都小於等於該結點的值。
結點的右子樹所有結點的值都大於該結點的值。
結點的左右子樹同樣都必須是二叉搜尋樹。

一種錯誤解法

初看這個問題，容易這麼實現：假定當前結點值為 k，對於二叉樹中每個結點，判斷其左孩子的值是否小於 k，其右孩子的值是否大於 k。如果所有結點都滿足該條件，則該二叉樹是一棵二叉搜尋樹。實現程式碼如下：

int isBSTError(BTNode *root)
{
if (!root) return 1;

if (root->left && root->left->value >= root->value)
return 0;

if (root->right && root->right->value < root->value)
return 0;

if (!isBSTError(root->left) || !isBSTError(root->right))
return 0;

return 1;
}
複製程式碼

很不幸，這種做法是錯誤的，如下面這棵二叉樹滿足上面的條件，但是它並不是二叉搜尋樹。

10
/\
515-------- binary tree(1) 符合上述條件的二叉樹，但是並不是二叉搜尋樹。
/\
620

複製程式碼

解1：蠻力法

上面的錯誤解法是因為判斷不完整導致，可以這樣來判斷：

判斷結點左子樹最大值是否大於等於結點的值，如果是，則該二叉樹不是二叉搜尋樹，否則繼續下一步判斷。。
判斷右子樹最小值是否小於或等於結點的值，如果是，則不是二叉搜尋樹，否則繼續下一步判斷。
遞迴判斷左右子樹是否是二叉搜尋樹。（程式碼中的 bstMax 和 bstMin 函式功能分別是返回二叉樹中的最大值和最小值結點，這裡假定二叉樹為二叉搜尋樹，實際返回的不一定是最大值和最小值結點）

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 < root->value)
return 0;

if (!isBSTUnefficient(root->left) || !isBSTUnefficient(root->right))
return 0;

return 1;
}
複製程式碼

解2：一次遍歷法

以前面提到的 binary tree(1) 為例，當我們遍歷到結點 15 時，我們知道右子樹結點值肯定都 >=10 。當我們遍歷到結點 15 的左孩子結點 6 時，我們知道結點 15 的左子樹結點值都必須在 10 到 15 之間。顯然，結點 6 不符合條件，因此它不是一棵二叉搜尋樹。

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);
}
複製程式碼

解3：中序遍歷解法

還可以模擬樹的中序遍歷來判斷BST，可以直接將中序遍歷的結果存到一個輔助陣列，然後判斷陣列是否有序即可判斷是否是BST。當然，我們可以不用輔助陣列，在遍歷時通過保留前一個指標 prev ，據此來實現判斷BST的解法，初始時 prev = NULL 。

int isBSTInOrder(BTNode *root, BTNode *prev) 
{ 
if (!root) return 1; 

if (!isBSTInOrder(root->left, prev)) 
return 0; 

if (prev && root->value < prev->value) 
return 0; 

return isBSTInOrder(root->right, root); 
} 
複製程式碼

1.2 判斷二叉樹是否是完全二叉樹

題：給定一棵二叉樹，判斷該二叉樹是否是完全二叉樹(完全二叉樹定義：若設二叉樹的深度為 h ，除第 h 層外，其它各層 (1～h-1) 的結點數都達到最大個數，第 h 層所有的結點都連續集中在最左邊，這就是完全二叉樹，如下圖所示）。

解1：常規解法-中序遍歷

先定義一個 滿結點 的概念：即一個結點存在左右孩子結點，則該結點為滿結點。在程式碼中定義變數 flag 來標識是否發現非滿結點，為1表示該二叉樹存在非滿結點。完全二叉樹如果存在非滿結點，則根據層序遍歷佇列中剩下結點必須是葉子結點，且如果一個結點的左孩子為空，則右孩子結點也必須為空。

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;
}
複製程式碼

解2：更簡單的方法-判斷結點序號法

更簡單的方法是判斷結點序號法，因為完全二叉樹的結點序號都是有規律的，如結點 i 的左右子結點序號為 2i+1 和 2i+2 ，如根結點序號是 0 ，它的左右子結點序號是 1 和 2 (如果都存在的話)。我們可以計算二叉樹的結點數目，然後依次判斷所有結點的序號，如果不是完全二叉樹，那肯定會存在結點它的序號大於等於結點數目的。如前面提到的 binary tree(1) 就不是完全二叉樹。

10(0)
/\
5(1) 15(2)- 結點數目為5，如果是完全二叉樹結點最大的序號應該是4，而它的是6，所以不是。
/\
6(5) 20(6)
複製程式碼

實現程式碼如下：

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));
}
複製程式碼

1.3 判斷平衡二叉樹

題：判斷一棵二叉樹是否是平衡二叉樹。所謂平衡二叉樹，指的是其任意結點的左右子樹高度之差不大於1。

__2__
/\
14---- 平衡二叉樹示例
\/ \
356
複製程式碼

解1：自頂向下方法

判斷一棵二叉樹是否是平衡的，對每個結點計算左右子樹高度差是否大於1即可，時間複雜度為 O(N^2) 。

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);
}
複製程式碼

解2：自底向上方法

因為解1會重複的遍歷很多結點，為此我們可以採用類似後序遍歷的方式，自底向上來判斷左右子樹的高度差，這樣時間複雜度為 O(N) 。

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;
}
複製程式碼

1.4 判斷兩棵二叉樹是否同構

題：給定兩棵二叉樹，根結點分別為 t1 和 t2 ，判定這兩棵二叉樹是否同構。所謂二叉樹同構就是指它們的結構相同，如下二叉樹 (1) 和 (2) 是同構的，而它們和 (3) 是不同結構的：

596
/ \/ \/ \
1271259
 / \/ \\
435810

二叉樹(1)二叉樹(2)二叉樹(3)

複製程式碼

解：二叉樹結構是否相同，還是遞迴實現，先判斷根結點是否同構，然後再判斷左右子樹。

int isOmorphism(BTNode *t1, BTNode *t2)
{
if (!t1 || !t2)
return (!t1) && (!t2);

return isOmorphism(t1->left, t2->left) && isOmorphism(t1->right, t2->right);
}
複製程式碼

2 構建類問題

構建類問題主要是使用二叉樹的兩種遍歷順序來確定二叉樹的另外一種遍歷順序問題。在上一篇文章中我們分析過二叉樹的先序、中序、後序遍歷的遞迴和非遞迴實現。那麼，是否可以根據先序、中序或者先序、後序或者中序、後序唯一確定一棵二叉樹呢？

答案是在沒有重複值的二叉樹中，根據先序遍歷和後序遍歷無法唯一確定一棵二叉樹，而根據先序、中序或者中序、後序遍歷是可以唯一確定一棵二叉樹的。

1）先序和後序遍歷無法唯一確定一棵二叉樹

一個簡單的例子如下，這兩棵二叉樹的先序遍歷和後序遍歷相同，由此可以證明先序遍歷和後序遍歷無法唯一確定一棵二叉樹。

11
 //
22
\/
 33
 
先序遍歷： 1 2 3
後序遍歷： 3 2 1
複製程式碼

2）先序和中序遍歷可以唯一確定二叉樹

簡單證明：因為先序遍歷的第一個元素是根結點，該元素將二叉樹中序遍歷序列分成兩部分，左邊（假設有L個元素）表示左子樹，若左邊無元素，則說明左子樹為空；右邊（假設有R個元素）是右子樹，若為空，則右子樹為空。根據前序遍歷中"根-左子樹-右子樹"的順序，則由從先序序列的第二元素開始的L個結點序列和中序序列根左邊的L個結點序列構造左子樹，由先序序列最後R個元素序列與中序序列根右邊的R個元素序列構造右子樹。

3)中序和後序遍歷可以唯一確定二叉樹

簡單證明: 假定二叉樹結點數為 n ，假定中序遍歷為 S ₁ , S ₂ , ..., S _n ，而後序遍歷為 P ₁ , P ₂ , ..., P _n ，因為後序遍歷最後一個結點 P _n 是根結點，則可以根據 P _n 將中序遍歷分為兩部分，則其中左邊L個結點是左子樹結點，右邊R個結點是右子樹結點，則後序遍歷中的 1~L 個結點是左子樹的後序遍歷，由此 P _L 是左子樹的根，與前面同理可以將中序遍歷分成兩部分，直到最終確定該二叉樹。

2.1 根據先序、中序遍歷構建二叉樹

題：給定一棵二叉樹的先序和中序遍歷序列，請構建該二叉樹（注：二叉樹沒有重複的值）。

先序遍歷： 7 10 4 3 1 2 8 11
中序遍歷： 4 10 3 1 7 11 8 2
二叉樹如下：
7
/\
102
/\/
438
\/
111

複製程式碼

解：根據前面的分析來解這個問題。

先序遍歷的第一個結點總是根結點。如上圖中的二叉樹，根結點為 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 為陣列大小。

/**
 * 輔助函式，查詢根結點在中序遍歷中的位置。
 */
int findBTRootIndex(int inorder[], int count, int rootVal)
{
int i;
for (i = 0; i < count; i++) {
if (inorder[i] == rootVal)
return i;
}
return -1;
}

/**
/**
 * 根據先序和中序遍歷構建二叉樹
 */
BTNode *buildBTFromPreInOrder(int preorder[], int inorder[], int n, int offset, int count)
{
if (n == 0) return NULL;

int rootVal = preorder[0];
int rootIndex = findBTRootIndex(inorder, count, rootVal);
int leftCount = rootIndex - offset; // 左子樹結點數目
int rightCount = n - leftCount - 1; // 右子樹結點數目

BTNode *root = btNewNode(rootVal);
root->left = buildBTFromPreInOrder(preorder+1, inorder, leftCount, offset, count);
root->right = buildBTFromPreInOrder(preorder+leftCount+1, inorder, rightCount, offset+leftCount+1, count);
return root;
}
複製程式碼

2.2 根據中序、後序遍歷構建二叉樹

題：給定一棵二叉樹的中序和後序遍歷序列，請構建該二叉樹（注：二叉樹沒有重複的值）。

中序遍歷： 4 10 3 1 7 11 8 2
後序遍歷： 4 1 3 10 11 8 2 7
二叉樹如下：
7
/\
102
/\/
438
\/
111
複製程式碼

解：跟前面一題類似，只是這裡根結點是從後序遍歷陣列的最後一個元素取。

/**
 * 根據中序和後序遍歷構建二叉樹
 */
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;
}
複製程式碼

3 儲存類問題

3.1 二叉搜尋樹儲存和恢復

題：設計一個演算法，將一棵二叉搜尋樹（BST）儲存到檔案中，需要能夠從檔案中恢復原來的二叉搜尋樹，注意演算法的時空複雜度。

30
/\
2040
// \
 103550
複製程式碼

思路

二叉樹遍歷演算法有先序遍歷、中序遍歷、後序遍歷演算法等。但是它們中間哪一種能夠用於儲存BST到檔案中並從檔案中恢復原來的BST，這是個要考慮的問題。

假定用中序遍歷，因為這棵BST的中序遍歷為 10 20 30 35 40 50 ，可能的結構是下面這樣，因此 中序遍歷不符合要求 。

50
/
40 
/
35
/
30
/
20
 /
10
複製程式碼

既然中序遍歷不行，後序遍歷如何？後序遍歷該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) 。

/**
 * 儲存二叉樹到檔案中-使用先序遍歷
 */
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;
}
複製程式碼

3.2 二叉樹儲存和恢復

題：設計一個演算法能夠實現二叉樹（注意，不是二叉搜尋樹BST）儲存和恢復。

解：3.1節提到過使用先序遍歷可以儲存和恢復二叉搜尋樹，而這個題目是針對二叉樹，並不是BST，所以不能用前面的方式。不過，我們可以採用先序遍歷的思想，只是在這裡需要改動。為了能夠在重構二叉樹時結點能夠插入到正確的位置，在使用先序遍歷儲存二叉樹到檔案中的時候需要把 NULL 結點也儲存起來（可以使用特殊符號如 # 來標識 NULL 結點）。

注意：本題採用 # 儲存 NULL 結點的方法存在缺陷，如本方法中二叉樹結點值就不能是 # 。如果要能儲存各種字元，則需要採用其他方法來實現了。

30
/\
1020
 //\
504535
複製程式碼

如上面這棵二叉樹，儲存到檔案中則為 30 10 50 # # # 20 45 # # 35 # # 。於是，儲存和恢復實現的程式碼如下：

/**
 * 儲存二叉樹到檔案中
 */
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;
}
複製程式碼

4 查詢類問題

查詢類問題主要包括：查詢二叉樹/二叉搜尋樹的最低公共祖先結點，或者是二叉樹中的最大的子樹且該子樹為二叉搜尋樹等。

4.1 二叉搜尋樹最低公共祖先結點

題：給定一棵二叉搜尋樹(BST)，找出樹中兩個結點的最低公共祖先結點(LCA)。如下面這棵二叉樹結點 2 和結點 8 的 LCA 是 6，而結點 4 和結點 2 的 LCA 是 2。

______6______
/\
__2____8__
/\/\
0479
/\
35

複製程式碼

解：我們從頂往下遍歷二叉搜尋樹時，對每個遍歷到的結點，待求LCA的兩個結點可能有如下四種分佈情況：

1）兩個結點都在樹的左子樹中： LCA一定在當前遍歷結點的左子樹中。
2）兩個結點都在樹的右子樹中： LCA一定在當前遍歷結點右子樹中。
3）一個結點在樹的左邊，一個結點在樹的右邊： LCA就是當前遍歷的結點。
4）當前結點等於這兩個結點中的一個： LCA也是當前遍歷的結點。

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 < q->value ? p->value : q->value;

if (maxValue < root->value) {
return bstLCA(root->left, p, q);
} else if (minValue > root->value) {
return bstLCA(root->right, p, q);
} else {
return root;
}
}
複製程式碼

4.2 二叉樹(不一定是BST）最低公共祖先結點

題：給定二叉樹中的兩個結點，輸出這兩個結點的最低公共祖先結點（LCA）。 注意，該二叉樹不一定是二叉搜尋樹。

_______3______
/\
___5_____1__
/\/\
6208
/\
74
複製程式碼

解1：自頂向下方法

因為不一定是BST，所以不能根據值大小來判斷，不過總體思路是一樣的：我們可以從根結點出發，判斷當前結點的左右子樹是否包含這兩個結點。

如果左子樹包含兩個結點，則它們的最低公共祖先結點也一定在左子樹中。
如果右子樹包含兩個結點，則它們的最低公共祖先結點也一定在右子樹中。
如果一個結點在左子樹，而另一個結點在右子樹中，則當前結點就是它們的最低公共祖先結點。

因為對每個結點都要重複判斷結點 p 和 q 的位置，總的時間複雜度為 O(N^2) ，為此，我們可以考慮找一個效率更高的方法。

/**
 * 二叉樹最低公共祖先結點-自頂向下解法 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);
}
複製程式碼

解2：自底向上方法

因為自頂向下方法有很多重複的判斷，於是有了這個自底向上的方法。自底向上遍歷結點，一旦遇到結點等於 p 或者 q ，則將其向上傳遞給它的父結點。父結點會判斷它的左右子樹是否都包含其中一個結點，如果是，則父結點一定是這兩個結點 p 和 q 的 LCA。如果不是，我們向上傳遞其中的包含結點 p 或者 q 的子結點，或者 NULL (如果左右子樹都沒有結點p或q)。該方法時間複雜度為O(N)。

/**
 * 二叉樹最低公共祖先結點-自底向上解法 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不在子樹中
}
複製程式碼

4.3 二叉樹的最大二叉搜尋子樹

題：找出二叉樹中最大的子樹，該子樹為二叉搜尋樹。所謂最大的子樹就是指結點數目最多的子樹。

___10___
/\
_5_15
/\\
187


___10____
/\
_5_15-------- subtree (1)
/\
18 

_5_
/\-------- subtree (2)
18 
複製程式碼

根據維基百科對子樹的定義，一棵二叉樹T的子樹由T的某個結點和該結點所有的後代構成。也就是說，該題目中， subtree(2) 才是正確的答案，因為 subtree(1) 不包含結點7，不滿足子樹的定義。

解1：自頂向下解法

最自然的解法是以根結點開始遍歷二叉樹所有的結點，判定以當前結點為根的子樹是否是BST，如果是，則該結點為根的BST就是最大的BST。如果不是，遞迴呼叫左右子樹，返回其中包含較多結點的子樹。

/**
 * 查詢二叉樹最大的二叉搜尋子樹-自頂向下方法
 */
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;
}
複製程式碼

解2：自底向上解法

自頂向下的解法時間複雜度為 O(N^2) ，每個結點都要判斷是否滿足BST的條件，可以用從底向上方法優化。我們在判斷上面結點為根的子樹是否是BST之前已經知道底部結點為根的子樹是否是BST，因此只要以底部結點為根的子樹不是BST，則以它上面結點為根的子樹一定不是BST。我們可以記錄子樹包含的結點數目，然後跟父結點所在的二叉樹比較，來求得最大BST子樹。

/**
 * 查詢二叉樹最大的二叉搜尋子樹-自底向上方法
 */
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;
}
複製程式碼

5 距離類問題

5.1 二叉樹兩個結點之間的最短距離

題：已知二叉樹中兩個結點，求這兩個結點之間的最短距離（注：最短距離是指從一個結點到另一個結點需要經過的邊的條數）。

___1___
/\
23
/\/\
4567
\
8
Distance(4, 5) = 2
Distance(4, 6) = 4
Distance(3, 4) = 3
Distance(2, 4) = 1
Distance(8, 5) = 5
複製程式碼

解：兩個結點的距離比較好辦，先求出兩個結點的最低公共祖先結點（LCA），然後計算 LCA 到兩個結點的距離之和即可，時間複雜度 O(N) 。

/**
 * 計算二叉樹兩個結點最短距離
 */
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;
}
複製程式碼

5.2 二叉搜尋樹兩個結點的最短距離

題：求一棵二叉搜尋樹中的兩個結點的最短距離。

解：與前面不同的是，這是一棵BST，那麼我們可以使用二叉搜尋樹的特點來簡化距離計算流程，當然直接用 5.1 的方法是完全OK的，因為它是通用的計算方法。

/**
 * 計算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);
}
複製程式碼

5.3 二叉樹中結點的最大距離

題：寫一個程式求一棵二叉樹中相距最遠的兩個結點之間的距離。

解：《程式設計之美》上有這道題，這題跟前面不同，要求相距最遠的兩個結點的距離，而且並沒有指定兩個結點位置。計算一個二叉樹的最大距離有兩個情況:

1）路徑為左子樹的最深節點 -> 根節點 -> 右子樹的最深節點。
2）路徑不穿過根節點，而是左子樹或右子樹的最大距離路徑，取其大者。

___10___
/\
_5_15------ 第1種情況
/\\
187

10
/
5
/\------ 第2種情況
18
/\
23
複製程式碼

我們定義函式 maxDistanceOfBT(BTNode *root) 用於計算二叉樹相距最遠的兩個結點的距離，可以遞迴的先計算左右子樹的最遠結點距離，然後比較左子樹最遠距離、右子樹最遠距離以及左右子樹最大深度之和，從而求出整個二叉樹的相距最遠的兩個結點的距離。

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;
}
複製程式碼

5.4 二叉樹最大寬度

題：給定一棵二叉樹，求該二叉樹的最大寬度。二叉樹的寬度指的是每一層的結點數目。如下面這棵二叉樹，從上往下1-4層的寬度分別是 1，2，3，2 ，於是它的最大寬度為3。

1
/\
23
/\\
458 
/\
67
複製程式碼

解1：層序遍歷法

最容易想到的方法就是使用層序遍歷，然後計算每一層的結點數，然後得出最大結點數。該方法時間複雜度為 O(N^2) 。當然如果優化為使用佇列來實現層序遍歷，可以得到 O(N) 的時間複雜度。

/**
 * 二叉樹最大寬度
 */
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);
}
複製程式碼

解2：先序遍歷法

我們可以先建立一個大小為二叉樹高度 h 的輔助陣列來儲存每一層的寬度，初始化為0。通過先序遍歷的方式來遍歷二叉樹，並設定好每層的寬度。最後，從這個輔助陣列中求最大值即是二叉樹最大寬度。

/**
 * 二叉樹最大寬度-先序遍歷法
 */
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 < h; i++) {
if (count[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);
}
複製程式碼

6 混合類問題

此類問題主要考察二叉樹和連結串列/陣列等結合，形式偏新穎。

6.1 根據有序陣列構建平衡二叉搜尋樹

題：給定一個有序陣列，陣列元素升序排列，試根據該陣列元素構建一棵平衡二叉搜尋樹（Balanced Binary Search Tree）。所謂平衡的定義，就是指二叉樹的子樹高度之差不能超過1。

__3__
/\
15---- 平衡二叉搜尋樹示例
\/ \
246

複製程式碼

解：如果要從一個有序陣列中選擇一個元素作為根結點，應該選擇哪個元素呢？我們應該選擇有序陣列的中間元素作為根結點。選擇了中間元素作為根結點並建立後，剩下的元素分為兩部分，可以看作是兩個陣列。這樣剩下的元素在根結點左邊的作為左子樹，右邊的作為右子樹。

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;
}
複製程式碼

6.2 有序單向連結串列構建平衡二叉搜尋樹

題：給定一個有序的單向連結串列，構建一棵平衡二叉搜尋樹。

解：最自然的想法是先將連結串列中的結點的值儲存在陣列中，然後採用 6.1 中方法實現，時間複雜度為 O(N) 。我們還可以採用自底向上的方法，在這裡我們不再需要每次查詢中間元素。

下面程式碼依舊需要連結串列長度作為引數，計算連結串列長度時間複雜度為O(N)，演算法時間複雜度也為O(N)，所以總的時間複雜度為O(N)。程式碼中需要注意的是每次呼叫 sortedList2BST 函式時， list 位置都會變化，呼叫完函式後 list 總是指向 mid+1 的位置（如果滿足返回條件，則 list 位置不變）。

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;
}
複製程式碼

例如連結串列只有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)，將其轉換為雙向的有序迴圈連結串列。

解：如圖所示，需要將 BST 的左右孩子指標替換成連結串列的 prev 和 next 指標，分別指向雙向連結串列的前一個和後一個結點。相信大多數人第一反應就是中序遍歷這棵二叉樹，同時改變樹中結點的 left 和 right 指標。這裡需要額外考慮的是如何將最後一個結點的 right 指標指向第一個結點，如下圖所展示的那樣。

以中序遍歷遍歷一棵二叉樹的時候，每遍歷到一個結點，我們就可以修改該結點的left指標指向前一個遍歷到的結點，因為在後續操作中我們不會再用到 left 指標；與此同時，我們還需要修改前一個遍歷結點的 right 指標，讓前一個遍歷結點的 right 指標指向當前結點。比如我們遍歷到結點2，則我們修改結點2的 left 指標指向結點1，同時需要修改結點1的 right 指標指向結點2。需要注意一點，這裡的前一個遍歷結點不是當前結點的父結點，而是當前結點的前一個比它小的結點。

看似問題已經解決，慢著，我們其實落下了重要的兩步。1）我們沒有對頭結點head賦值。 2）最後一個結點的right指標沒有指向第一個結點。

解決這兩個問題的方案非常簡單：在每次遞迴呼叫的時候，更新當前遍歷結點的 right 指標讓其指向頭結點 head ，同時更新頭結點 head 的 left 指標讓其指向當前遍歷結點。當遞迴呼叫結束的時候，連結串列的頭尾結點會指向正確的位置。不要忘記只有一個結點的特殊情況，它的 left 和 right 指標都是指向自己。

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); 
}
複製程式碼

這個解法非常的精巧，因為該演算法是對中序遍歷的一個改進，因此它的時間複雜度為O(N)，N為結點數目。當然，相比中序遍歷，我們在每次遞迴呼叫過程中增加了額外的賦值操作。

資料結構和演算法面試題系列—二叉樹面試題彙總

1 判斷類問題

1.1 判斷一棵二叉樹是否是二叉搜尋樹(BST)

一種錯誤解法

解1：蠻力法

解2：一次遍歷法

解3：中序遍歷解法

1.2 判斷二叉樹是否是完全二叉樹

解1：常規解法-中序遍歷

解2：更簡單的方法-判斷結點序號法

1.3 判斷平衡二叉樹

解1：自頂向下方法

解2：自底向上方法

1.4 判斷兩棵二叉樹是否同構

2 構建類問題

1）先序和後序遍歷無法唯一確定一棵二叉樹

2）先序和中序遍歷可以唯一確定二叉樹

3)中序和後序遍歷可以唯一確定二叉樹

2.1 根據先序、中序遍歷構建二叉樹

2.2 根據中序、後序遍歷構建二叉樹

3 儲存類問題

3.1 二叉搜尋樹儲存和恢復

思路

3.2 二叉樹儲存和恢復

4 查詢類問題

4.1 二叉搜尋樹最低公共祖先結點

4.2 二叉樹(不一定是BST）最低公共祖先結點

解1：自頂向下方法

解2：自底向上方法

4.3 二叉樹的最大二叉搜尋子樹

解1：自頂向下解法

解2：自底向上解法

5 距離類問題

5.1 二叉樹兩個結點之間的最短距離

5.2 二叉搜尋樹兩個結點的最短距離

5.3 二叉樹中結點的最大距離

5.4 二叉樹最大寬度

解1：層序遍歷法

解2：先序遍歷法

6 混合類問題

6.1 根據有序陣列構建平衡二叉搜尋樹

6.2 有序單向連結串列構建平衡二叉搜尋樹

6.3 二叉搜尋樹轉換為有序迴圈連結串列

看似問題已經解決，慢著，我們其實落下了重要的兩步。1）我們沒有對頭結點head賦值。 2）最後一個結點的right指標沒有指向第一個結點。

您可能也會喜歡…