二叉樹常見面試題

一、常見題型

1. 求兩個節點的最近公共祖先；

2. 求二叉樹中最遠的兩個節點的距離；

4. 判斷一棵樹是否是完全二叉樹 ；

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

6.求二叉樹的寬度；

7. 判斷一棵二叉樹是否是平衡二叉樹；

8.判斷一顆二叉樹是否是另一顆樹的子樹。

求兩個節點的最近公共祖先可分為三種情況，分別為：

（1）搜索二叉樹，根據搜索二叉樹的性質，左子樹的所有節點比根節點小，右子樹的所有節點比跟節點大。

如果兩個節點都比根節點小，則遞歸左子樹 ；

如果兩個節點都比跟節點大，則遞歸右子樹 ；

否則，兩個節點一個在左子樹，一個在右子樹，則當前節點就是最近公共祖先節點。

1 Node* GetAncestor(Node* root, Node* x1, Node* x2)//1.該二叉樹為搜索二叉樹
2 {
3 assert(x1 && x2);
4 if (x1->_data <= root->_data && x2->_data <= root->_data)
5 {
6 return GetAncestor(root->_left, x1, x2);//兩個節都小於根節點，最近公共祖先在左子樹中
7 }
8 else if (x1->_data > root->_data && x2->_data > root->_data)
9 {
10 return GetAncestor(root->_right, x1, x2);//兩個節都大於根節點，最近公共祖先在左子樹中
11 }
12 else
13 return root; //一個在左子樹，一個在右子樹，找到公共祖先
14
15 }

（2）三叉鏈，二叉樹節點有指向父節點的指針。首先給出node1的父節點node1->_parent，然後將node1的所有父節點依次和node2->parent作比較，如果發現兩個節點相等，則該節點就是最近公共祖先，直接將其返回。如果沒找到相等節點，則將node2的所有父節點依次和node1->_parent->_parent作比較......直到node1->_parent==NULL。代碼如下：

1 struct BinaryNode //節點的結構
2 {
3 BinaryNode* _left;
4 BinaryNode* _right;
5 BinaryNode* _parent;
6 int _data;
7
8 BinaryNode(const int& data)
9 :_data(data)
10 , _left(NULL)
11 , _right(NULL)
12 , _parent(NULL)
13 {}
14 };

1 Node * GetLastCommonAncestor(Node * root, Node * node1, Node * node2)
2 {
3 Node * temp;
4 while (node1 != NULL)
5 {
6 node1 = node1->_parent;
7 temp = node2;
8 while (temp != NULL)
9 {
10 if (node1 == temp->_parent)
11 return node1;
12 temp = temp->_parent;
13 }
14 }
15 }

該演算法時間複雜度為O(n^2)，可用另一種O(n)的演算法：

給定的兩個節點都含有父節點，因此，可將這兩個節點看做是兩個鏈表的頭結點，將求兩個節點的最近公共祖先節點轉化為求兩鏈表的交點，這兩個鏈表的尾節點都是根節點。

1 int Hight(BinaryNode* root, BinaryNode* node)
2 {
3 int len = 0;
4 for (; node != NULL; node = node->_parent)
5 len++;
6
7 return len;
8 }
9 BinaryNode* GetLastCommonAncestor(BinaryNode* root, BinaryNode* node1, BinaryNode* node2)
10 {
11
12 if (root == NULL || node1 == NULL || node2==NULL)
13 return NULL;
14
15 int len1 = Hight(root,node1);
16 int len2 = Hight(root,node2);
17
19 for (; len1 > len2; len1--)
20 node1 = node1->_parent;
21 for (; len2 > len1; len2--)
22 node2 = node2->_parent;
23
24 while (node1 && node2 && node1 != node2)
25 {
26 node1 = node1->_parent;
27 node2 = node2->_parent;
28 }
29
30 if (node1 == node2)
31 return node1;
32 else
33 return NULL;
34 }

（3）普通二叉樹，這種情況可採用與搜索二叉樹類似的解法

從根節點開始遍歷，如果node1和node2中的任一個和root匹配，那麼與root匹配的節點就是最低公共祖先。 如果都不匹配，則分別遞歸左、右子樹，如果有一個 節點出現在左子樹，並且另一個節點出現在右子樹，則root就是最低公共祖先. 如果兩個節點都出現在左子樹，則說明最低公共祖先在左子樹中，否則在右子樹。

1 Node* GetAncestor(Node* root, Node* x1, Node* x2)
2 {
3 assert(x1 && x2);
4 if (root == NULL) {
5 return NULL;
6 }
7 if (root == x1 || root == x2) //如果兩個節點是父子關係，其中的一個節點為公共祖先
8 {
9 return root;
10 }
11 bool x1inleft, x2inleft, x1inright, x2inright;
12 x1inleft = JudgeNode(root->_left, x1); //判斷x1是否在左子樹
13 x1inright = JudgeNode(root->_right x1); //判斷x1是否在右子樹
14 assert(x1inleft || x1inright); //至少有一個為真
15 x2inleft = JudgeNode(root->_left, x2); //判斷x2是否在左子樹
16 x2inright = JudgeNode(root->_right, x2); //判斷x2是否在右子樹
17 assert(x2inleft || x2inright); //至少有一個為真
18 if ((x1inleft && x2inright) || (x1inright && x2inright))
19 {
20 return root; //一個在左子樹，一個在右子樹，找到公共祖先
21 }
22 else if (x1inleft && x2inleft) //兩個節都在左子樹中,最近公共祖先在左子樹中
23 {
24 return GetAncestor(root->_left, x1, x2);
25 }
26 else { //兩個節都在右子樹中,最近公共祖先在右子樹中
27 return GetAncestor(root->_right, x1, x2);
28 }
29 }

上述方法時間複雜度為O（N^2），下面的方法時間複雜度為O（N）,但是需要額外的空間來存儲路徑。

1)找到從根到node1的路徑，並存儲在一個向量或數組中。

2)找到從根到node2的路徑，並存儲在一個向量或數組中。

3)遍歷這兩條路徑，直到遇到一個不同的節點，則前面的那個即為最低公共祖先.

1 bool GetNodePaths(Node* root, Node* node, stack<Node *>& s)
2 {
3 if (root == NULL)
4 {
5 return false;
6 }
7 s.push(root);
8 if (root == node)
9 {
10 return node;
11 }
12 bool inleft = GetNodePaths(root->_left, node, s);
13 if (inleft)
14 {
15 return true;
16 }
17 bool inright = GetNodePaths(root->_right, node, s);
18 if (inright)
19 {
20 return true;
21 }
22 s.pop;
23 return false;
24 }
25 Node* GetAncestor(Node* root, Node* x1, Node* x2);
26 {
27 assert(x1 && x2);
28 stack<Node*> paths1, paths2;
29 if (!GetNodePaths(root->_left, x1, paths1) || !GetNodePaths(root->_right, x2, paths2))
30 {
31 return NULL;
32 }
33 }

2.最遠的兩個節點的距離

第一種情況最遠的兩個節點的距離為它們到根節點的路徑長度之和，又有可能距離最遠的兩個節點之間的路徑不經過根節點，如圖所示：

所以不要考慮不全，直接用兩個子樹的的高度相加來表示最遠的兩個節點的距離。有兩種方法求解：

還是要藉助兩個子樹的高度求解，但是要遞歸整棵樹，如果子樹中出現第二種情況要更新最大距離，時間複雜度為O（N^2）。

1 //求二叉樹中最遠的兩個節點的距離
2 size_t MaxLen
3 {
4 size_t maxlen = 0;
5 _MaxLen(_root, maxlen);
6 return maxlen;
7 }
8 void _MaxLen(Node* root, size_t maxlen) //O(N^2)
9 {
10 if (root == NULL)
11 {
12 return 0;
13 }
14 int leftdepth = Depth(root->_left);
15 int rightdepth = Depth(root->_right);
16 if (leftdepth + rightdepth > maxlen)
17 {
18 maxlen = leftdepth + rightdepth;
19 }
20 _MaxLen(root->_left, maxlen);
21 _MaxLen(root->_right, maxlen);
22 }

另一種時間複雜度為O（N）的解法：

1 size_t _MaxLen(Node* root, size_t maxlen) //O(N)
2 {
3 if (root == NULL)
4 {
5 return;
6 }
7 size_t left = _MaxLen(root->_left, maxlen);
8 size_t right = _MaxLen(root->_right, maxlen);
9 if (right+left>maxlen)
10 {
11 maxlen = right + left;
12 }
13 return left > right ? left + 1 : right + 1;
14 }

3. 前序遍歷和中序遍歷重建二叉樹

這個題是要用一顆二叉樹的前序遍歷序列和中序遍歷序列，如：前序序列：1 2 3 4 5 6 - 中序序列 ：3 2 4 1 6 5，來重新構建二叉樹。可以利用前序序列和中序序列中根節點的位置特性作為重建依據。圖示解析過程如下：

創建右子樹的方法與左子樹的方法完全相同。當 prev 遍歷完前序序列，即二叉樹創建完成。代碼如下：

1 //由前序遍歷和中序遍歷重建二叉樹（如：前序序列：1 2 3 4 5 6 - 中序序列 ：3 2 4 1 6 5）
2 Node* RebulidTree(char* prev, char* inbgein, char* inend)
3 {
4 assert(prev && inbgein && inend);
5 if (inbgein > inend || prev == "")
6 {
7 return NULL;
8 }
9 Node* root = new Node(*prev); //先創建根節點
10 char* div = inbgein; //讓div查找根節點
11 while (div <= inend) {
12 if (*div == *prev)
13 {
14 if (inbgein <= div -1)
15 {
16 root->_left = RebulidTree(++prev, inbgein, div - 1);//遞歸創建左子樹
17 }
18 else {
19 root->_left = NULL;
20 }
21 if (div + 1 <= inend)
22 {
23 root->_right = RebulidTree(++prev, div + 1, inend);//遞歸創建右子樹
24 }
25 else {
26 root->_right = NULL;
27 }
28 break;
29 }
30 ++div;
31 }
32 return root;
33 }

4. 判斷一棵樹是否是完全二叉樹

完全二叉樹： 前n-1層都是滿的，第n層如有空缺，則是缺在右邊，即第n層的最右邊的節點，它的左邊是滿的，右邊是空的。

這是一個層序遍歷非遞歸法的變型題，同樣要藉助額外空間來臨時存儲節點。按照層序遍歷二叉樹，找到第一個只有非滿結點（這個節點只有兩種情況，孩子為空或者只有左沒有右），如果之後的節點還有非滿結點，則不是。

1 bool IsComplateTree(Node* root)
2 {
3 queue<Node*> q;
4 if (root)
5 {
6 q.push(root); //先將節點壓入隊列中
7 }
8 //這裡給一個tag是標記是否出現非滿節點
9 bool tag = true;
10 while (!q.empty)
11 {
12 Node* front = q.front;
13 q.pop;
14 //如果已經出現過非滿結點，則後面再出現有孩子的結點則一定不是完全二叉樹。
15 if (front->_left)
16 {
17 if (tag == false)
18 {
19 return false;
20 }
21 q.push(front->_left);
22 }
23 else {
24 tag = false;
25 }
26 if (front->_right)
27 {
28 if (tag == false)
29 {
30 return false;
31 }
32 q.push(front->_right);
33 }
34 else {
35 tag = false;
36 }
37 }
38 return true;
39 }

第二種思路：將所有的結點全部押入隊列中，每次判斷隊列的頭如果隊列頭為空了則跳出循環，如果此後隊列中還有元素則不是完全二叉樹。

1 bool IsCompleteTree(BinaryTreeNode *pRoot)
2 {
3 if(pRoot == NULL)
4 return false;
5
6 queue<BinaryTreeNode*> q;
7 q.push(pRoot);
8 BinaryTreeNode* pCur = q.front;
9 while(pCur != NULL)
10 {
11 q.pop;
12 q.push(pCur -> left);
13 q.push(pCur -> right);
14 pCur = q.front;
15 }
16
17 q.pop;//把空pop出來
18 //因為以經有一個空了，所以只要頭不為空就不是完全二叉樹
19 while(! q.empty)
20 {
21 if(q.front != NULL)
22 return false;
23 q.pop;
24 }
25 return true;
26 }

5. 將二叉搜索樹轉換成一個排序的雙向鏈表

與二叉樹的線索花化雷同

1 void _ToList(Node* cur, Node*& prev)
2 {
3 if (cur == NULL)
4 return;
5
6 _ToList(cur->_left, prev);
7 //
8 cur->_left = prev;
9 if(prev)
10 prev->_right = cur;
11
12 prev = cur;
13
14 _ToList(cur->_right, prev);
15 }
16
17 Node* ToList(Node* root)
18 {
19 Node* prev = NULL;
20 _ToList(root, prev);
21
22 Node* head = root;
23 while (head && head->_left)
24 {
25 head = head->_left;
26 }
27
28 return head;
29 }

6.求二叉樹的寬度

所謂二叉樹的寬度是指：二叉樹各層節點個數的最大值。

我們知道層序遍歷二叉樹是使用 queue 來實現的：每次列印一個節點之後，如果存在左右子樹，則把左右子樹壓入 queue，那麼此時的隊列中可能既包含當前層的節點，也包含下一層的節點。

而我們要求的是對於特定某一層的節點的個數，因此我們需要從頭結點開始，記錄每一層的個數，對於當前層的每一個節點，在彈出自身之後把其左右子樹壓入 queue，當把當前層全部彈出隊列之後，在隊列中剩下的就是下一層的節點。然後比較隊列的size和之前得到的maxWidth，取最大值即為隊列的寬度。最終隊列為空，得到的maxWidth就是二叉樹的寬度！

1 int Width(Node* root)
2 {
3 queue<Node*> q;
4 if (root)
5 q.push(root);
6 int maxwidth = 1;
7 while (!q.empty)
8 {
9 int length = q.size;
10 while (length-- > 0)
11 {
12 Node* front = q.front;
13 q.pop;
14 if (front->_left)
15 {
16 q.push(front->_left);
17 }
18 if (front->_right)
19 {
20 q.push(front->_right);
21 }
22 }
23 maxwidth = maxwidth > q.size ? maxwidth : q.size;
24 }
25 return maxwidth;
26 }

7. 二叉樹是否是平衡二叉樹

二叉樹中每一個節點的左右子樹高度之差均小於2即為平衡二叉樹。那麼當一顆二叉樹的所有子樹都是平衡二叉樹時，它本身必定為平衡二叉樹，用此思想可遞歸判斷二叉樹是否是平衡二叉樹。代碼如下：

1 //--判斷一棵二叉樹是否是平衡二叉樹
2 bool IsBalance(Node* root) //O(N^2)
3 {
4 if (root == NULL)
5 {
6 return false;
7 }
8 int left = Depth(root->_left);
9 int right = Depth(root->_right);
10 return abs(right - left) < 2 && IsBalance(root->_left) && IsBalance(root->_right);
11 }

這種方法藉助左右的高度比較來確定是否為二叉樹，需多次遍歷二叉樹，時間複雜度為O（N^2）。下面是一種O（N）的演算法：

1 bool IsBalance(Node* root, int& depth) //O(N)
2 {
3 if (root == NULL)
4 {
5 depth = 0;
6 return false
7 }
8 int leftdepth = 0;
9 if (IsBalance(root->_left, leftdepth) == false)
10 {
11 return false;
12 }
13 int rightdepth = 0;
14 if (IsBalance(root->_right, rightdepth) == false)
15 {
16 return false;
17 }
18 rightdepth > leftdepth ? depth + 1 : depth;
19 return abs(leftdepth - rightdepth) < 2;
20 }

8.二叉樹是否為另一顆樹的子樹

判斷一顆二叉樹是否是另一顆樹的子樹。

先在找二叉樹里找根節點，找到之後判斷後續的節點是否相等，如果相等，則為子樹。

1 bool JudgeNextTree(Node* next, Node* child) //兩棵樹的起始節點的值已經相等，在判斷其他節點是否相等
2 {
3 if (child == NULL)
4 {
5 return true;
6 }
7 if (next == NULL)
8 {
9 return false;
10 }
11 if (next->_data == child->_data) //
12 {
13 return JudgeNextTree(next->_left, child->_left) && JudgeNextTree(next->_right, child->_right);
14 }
15 else {
16 return false; //如果左右孩子都相等，則是子樹，否則不是
17 }
18 }
19 bool JudgeTree(Node* parent, Node* child) //判斷child是否為parent的子樹
20 {
21 if (child == NULL) //空樹是任何樹的子樹
22 {
23 return true;
24 }
25 if (parent == NULL) //空樹沒有除空樹的任何子樹
26 {
27 return false;
28 }
29 if (parent->_data == child->_data) //當前節點與要查找子樹的根節點相同時
30 {
31 return JudgeNextTree(parent, child); //從相等節點開始判斷是否為子樹
32 }
33 else if (JudgeTree(parent->_left, child->_left) == true) //判斷當前節點的左子樹是否與要查找子樹的根節點相同
34 {
35 return true;
36 }
37 else {
38 return JudgeTree(parent->_right, child->_right); //判斷當前節點的右子樹是否與要查找子樹的根節點相同
39 }
40 }

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！