深入淺出！二叉樹詳解，還包含C代碼

1. 前序遍歷，中序遍歷，后序遍歷；
2. 層次遍歷；
3. 求樹的結(jié)點數(shù)；
4. 求樹的葉子數(shù)；
5. 求樹的深度；
6. 求二叉樹第k層的結(jié)點個數(shù)；
7. 判斷兩棵二叉樹是否結(jié)構(gòu)相同；
8. 求二叉樹的鏡像；
9. 求兩個結(jié)點的最低公共祖先結(jié)點；
10. 求任意兩結(jié)點距離；
11. 找出二叉樹中某個結(jié)點的所有祖先結(jié)點；
12. 不使用遞歸和棧遍歷二叉樹；
13. 二叉樹前序中序推后序；
14. 判斷二叉樹是不是完全二叉樹；
15. 判斷是否是二叉查找樹的后序遍歷結(jié)果；
16. 給定一個二叉查找樹中的結(jié)點，找出在中序遍歷下它的后繼和前驅(qū)；
17. 二分查找樹轉(zhuǎn)化為排序的循環(huán)雙鏈表；
18. 有序鏈表轉(zhuǎn)化為平衡的二分查找樹；
19. 判斷是否是二叉查找樹。

1 前序遍歷，中序遍歷，后序遍歷；

1.1 前序遍歷

對于當(dāng)前結(jié)點，先輸出該結(jié)點，然后輸出它的左孩子，最后輸出它的右孩子。以上圖為例，遞歸的過程如下：

1. 輸出 1，接著左孩子；
2. 輸出 2，接著左孩子；
3. 輸出 4，左孩子為空，再接著右孩子；
4. 輸出 6，左孩子為空，再接著右孩子；
5. 輸出 7，左右孩子都為空，此時 2 的左子樹全部輸出，2 的右子樹為空，此時 1 的左子樹全部輸出，接著 1 的右子樹；
6. 輸出 3，接著左孩子；
7. 輸出 5，左右孩子為空，此時 3 的左子樹全部輸出，3 的右子樹為空，至此 1 的右子樹全部輸出，結(jié)束。

而非遞歸版本只是利用 stack 模擬上述過程而已，遞歸的過程也就是出入棧的過程。

/*?前序遍歷遞歸版?*/
void?PreOrderRec(Node?*?node)
{
????if?(node?==?nullptr)
????????return;
????cout?<data?<"?";???//?先輸出當(dāng)前結(jié)點???
????PreOrderRec(node->left);?????//?然后輸出左孩子
????PreOrderRec(node->right);????//?最后輸出右孩子
}

/*?前序遍歷非遞歸版?*/
void?PreOrderNonRec(Node?*?node)
{
????if?(node?==?nullptr)
????????return;

????stack?S;
????cout?<data?<"?";
????S.push(node);
????node?=?node->left;

????while?(!S.empty()?||?node)
????{
????????while?(node)
????????{
????????????cout?<data?<"?";?//?先輸出當(dāng)前結(jié)點??
????????????S.push(node);
????????????node?=?node->left;?????????//?然后輸出左孩子
????????}??????????????????????????????//?while?結(jié)束意味著左孩子已經(jīng)全部輸出

????????node?=?S.top()->right;?????????//?最后輸出右孩子
????????S.pop();
????}
}

1.2 中序遍歷

對于當(dāng)前結(jié)點，先輸出它的左孩子，然后輸出該結(jié)點，最后輸出它的右孩子。以（1.1）圖為例：

1. 1-->2-->4，4 的左孩子為空，輸出 4，接著右孩子；
2. 6 的左孩子為空，輸出 6，接著右孩子；
3. 7 的左孩子為空，輸出 7，右孩子也為空，此時 2 的左子樹全部輸出，輸出 2，2 的右孩子為空，此時 1 的左子樹全部輸出，輸出 1，接著 1 的右孩子；
4. 3-->5，5 左孩子為空，輸出 5，右孩子也為空，此時 3 的左子樹全部輸出，而 3 的右孩子為空，至此 1 的右子樹全部輸出，結(jié)束。

/*?中序遍歷遞歸版?*/
void?InOrderRec(Node?*?node)
{
????if?(node?==?nullptr)
????????return;

????InOrderRec(node->left);?????//?先輸出左孩子
????cout?<data?<"?";??//?然后輸出當(dāng)前結(jié)點
????InOrderRec(node->right);????//?最后輸出右孩子
}

/*?前序遍歷非遞歸版?*/
void?InOrderNonRec(Node?*?node)
{
????if?(node?==?nullptr)
????????return;

????stack?S;
????S.push(node);
????node?=?node->left;

????while?(!S.empty()?||?node)
????{
????????while?(node)
????????{
????????????S.push(node);
????????????node?=?node->left;
????????}?????????????????????????????//?while?結(jié)束意味著左孩子為空

????????cout?<data?<"?";?//?左孩子已經(jīng)全部輸出，接著輸出當(dāng)前結(jié)點
????????node?=?S.top()->right;????????//?左孩子全部輸出，當(dāng)前結(jié)點也輸出后，最后輸出右孩子
????????S.pop();
????}
}

1.3 后序遍歷

對于當(dāng)前結(jié)點，先輸出它的左孩子，然后輸出它的右孩子，最后輸出該結(jié)點。依舊以（1.1）圖為例：

1. 1->2->4->6->7，7 無左孩子，也無右孩子，輸出 7，此時 6 無左孩子，而 6 的右子樹也全部輸出，輸出 6，此時 4 無左子樹，而 4 的右子樹已全部輸出，接著輸出 4，此時 2 的左子樹全部輸出，且 2 無右子樹，輸出 2，此時 1 的左子樹全部輸出，接著轉(zhuǎn)向右子樹；
2. 3->5，5 無左孩子，也無右孩子，輸出 5，此時 3 的左子樹全部輸出，且 3 無右孩子，輸出 3，此時 1 的右子樹全部輸出，輸出 1，結(jié)束。

非遞歸版本中，對于一個結(jié)點，如果我們要輸出它，只有它既沒有左孩子也沒有右孩子或者它有孩子但是它的孩子已經(jīng)被輸出（由此設(shè)置 pre 變量）。若非上述兩種情況，則將該結(jié)點的右孩子和左孩子依次入棧，這樣就保證了每次取棧頂元素的時候,先依次遍歷左子樹和右子樹。

/*?后序遍歷遞歸版?*/
void?PostOrderRec(Node?*?node)
{
????if?(node?==?nullptr)
????????return;

????PostOrderRec(node->left);???//?先輸出左孩子
????PostOrderRec(node->right);??//?然后輸出右孩子
????cout?<data?<"?";??//?最后輸出當(dāng)前結(jié)點
}

/*?后序遍歷非遞歸版?*/
void?PostOrderNonRec(Node?*?node)
{
????if?(node?==?nullptr)
????????return;

????Node?*?pre?=?nullptr;
????stack?S;
????S.push(node);

????while?(!S.empty())
????{
????????node?=?S.top();

????????if?((!node->left?&&?!node->right)?||????????????????????//?第一個輸出的必是無左右孩子的葉子結(jié)點，只要第一個結(jié)點輸出，
????????????(pre &&?(pre == node->left || pre == node->right)))?//?以后的 pre 就不會是空。此處的判斷語句加入一個 pre，只是用來
????????{???????????????????????????????????????????????????????//?確?？梢哉_輸出第一個結(jié)點。
????????????cout?<data?<"?";??//?左右孩子都全部輸出，再輸出當(dāng)前結(jié)點
????????????pre?=?node;
????????????S.pop();
????????}
????????else
????????{
????????????if?(node->right)
????????????????S.push(node->right);??//?先進(jìn)右孩子，再進(jìn)左孩子，取出來的才是左孩子
????????????if?(node->left)
????????????????S.push(node->left);
????????}
????}
}

2 層次遍歷

void?LevelOrder(Node?*?node)
{
????Node?*?p?=?node;
????queue?Q;??//?隊列
????Q.push(p);

????while?(!Q.empty())
????{
????????p?=?Q.front();
????????cout?<data?<"?";
????????Q.pop();

????????if?(p->left)
????????????Q.push(p->left);??//?注意順序，先進(jìn)左孩子
????????if?(p->right)
????????????Q.push(p->right);
????}
}

3 求樹的結(jié)點數(shù)

int?CountNodes(Node?*?node)
{
????if?(node?==?nullptr)
????????return?0;

????return?CountNodes(node->left)?+?CountNodes(node->right)?+?1;
}

4 求樹的葉子數(shù)

int?CountLeaves(Node?*?node)
{
????if?(node?==?nullptr)
????????return?0;

????if?(!node->left?&&?!node->right)
????????return?1;

????return?CountLeaves(node->left)?+?CountLeaves(node->right);
}

5 求樹的深度

int?GetDepth(Node?*?node)
{
????if?(node?==?nullptr)
????????return?0;

????int?left_depth?=?GetDepth(node->left)?+?1;
????int?right_depth?=?GetDepth(node->right)?+?1;

????return?left_depth?>?right_depth???left_depth?:?right_depth;
}

6 求二叉樹第k層的結(jié)點個數(shù)

int?GetKLevel(Node?*?node,?int?k)
{
????if?(node?==?nullptr)
????????return?0;

????if?(k?==?1)
????????return?1;

????return?GetKLevel(node->left,?k?-?1)?+?GetKLevel(node->right,?k?-?1);
}

7 判斷兩棵二叉樹是否結(jié)構(gòu)相同

不考慮數(shù)據(jù)內(nèi)容。結(jié)構(gòu)相同意味著對應(yīng)的左子樹和對應(yīng)的右子樹都結(jié)構(gòu)相同。

bool?StructureCmp(Node?*?node1,?Node?*?node2)
{
????if?(node1?==?nullptr?&&?node2?==?nullptr)
????????return?true;
????else?if?(node1?==?nullptr?||?node2?==?nullptr)
????????return?false;

????return?StructureCmp(node1->left,?node2->left)?&&?Str1uctureCmp(node1->right,?node2->right);
}

8 求二叉樹的鏡像

對于每個結(jié)點，我們交換它的左右孩子即可。

void?Mirror(Node?*?node)
{
????if?(node?==?nullptr)
????????return;

????Node?*?temp?=?node->left;
????node->left?=?node->right;
????node->right?=?temp;

????Mirror(node->left);
????Mirror(node->right);
}

9 求兩個結(jié)點的最低公共祖先結(jié)點

最低公共祖先，即 LCA（Lowest Common Ancestor），見下圖：結(jié)點 3 和結(jié)點 4 的最近公共祖先是結(jié)點 2，即 LCA(3,4)=2。在此，需要注意到當(dāng)兩個結(jié)點在同一棵子樹上的情況，如結(jié)點 3 和結(jié)點 2 的最近公共祖先為 2，即 LCA(3,2)=2。同理 LCA(5,6)=4，LCA(6,10)=1。

Node?*?FindLCA(Node?*?node,?Node?*?target1,?Node?*?target2)
{
????if?(node?==?nullptr)
????????return?nullptr;
????if?(node?==?target1?||?node?==?target2)
????????return?node;

????Node?*?left?=?FindLCA(node->left,?target1,?target2);
????Node?*?right?=?FindLCA(node->right,?target1,?target2);
????if?(left?&&?right)??//?分別在左右子樹
????????return?node;

????return?left???left?:?right;??//?都在左子樹或右子樹
}

10 求任意兩結(jié)點距離

首先找到兩個結(jié)點的 LCA，然后分別計算 LCA 與它們的距離，最后相加即可。

int?FindLevel(Node?*?node,?Node?*?target)
{
????if?(node?==?nullptr)
????????return?-1;
????if?(node?==?target)
????????return?0;

????int?level?=?FindLevel(node->left,?target);??//?先在左子樹找
????if?(level?==?-1)
????????level?=?FindLevel(node->right,?target);??//?如果左子樹沒找到，在右子樹找

????if?(level?!=?-1)??//?找到了，回溯
????????return?level?+?1;

????return?-1;??//?如果左右子樹都沒找到
}

int?DistanceNodes(Node?*?node,?Node?*?target1,?Node?*?target2)
{
????Node?*?lca?=?FindLCA(node,?target1,?target2);??//?找到最低公共祖先結(jié)點
????int?level1?=?FindLevel(lca,?target1);?
????int?level2?=?FindLevel(lca,?target2);

????return?level1?+?level2;
}

11 找出二叉樹中某個結(jié)點的所有祖先結(jié)點

如果給定結(jié)點 5，則其所有祖先結(jié)點為 4,2,1。

bool?FindAllAncestors(Node?*?node,?Node?*?target)
{
????if?(node?==?nullptr)
????????return?false;
????if?(node?==?target)
????????return?true;

????if?(FindAllAncestors(node->left,?target)?||?FindAllAncestors(node->right,?target))??//?找到了
????{
????????cout?<data?<"?";
????????return?true;??//?回溯
????}

????return?false;??//?如果左右子樹都沒找到
}

12 不使用遞歸和棧遍歷二叉樹

1968 年，高德納（Donald Knuth）提出一個問題：是否存在一個算法，它不使用棧也不破壞二叉樹結(jié)構(gòu)，但是可以完成對二叉樹的遍歷？隨后 1979 年，James H. Morris 提出了二叉樹線索化，解決了這個問題。（根據(jù)這個概念我們又提出了一個新的數(shù)據(jù)結(jié)構(gòu)，即線索二叉樹，因線索二叉樹不是本文要介紹的內(nèi)容，所以有興趣的朋友請移步線索二叉樹）

前序，中序，后序遍歷，不管是遞歸版本還是非遞歸版本，都用到了一個數(shù)據(jù)結(jié)構(gòu)--棧，為何要用棧？那是因為其它的方式?jīng)]法記錄當(dāng)前結(jié)點的 parent,而如果在每個結(jié)點的結(jié)構(gòu)里面加個 parent 分量顯然是不現(xiàn)實的，而線索化正好解決了這個問題，其含義就是利用結(jié)點的右孩子空指針，指向該結(jié)點在中序序列中的后繼。下面具體來看看如何使用線索化來完成對二叉樹的遍歷。先看前序遍歷，步驟如下：

1. 如果當(dāng)前結(jié)點的左孩子為空，則輸出當(dāng)前結(jié)點并將其右孩子作為當(dāng)前結(jié)點；
2. 如果當(dāng)前結(jié)點的左孩子不為空，在當(dāng)前結(jié)點的左子樹中找到當(dāng)前結(jié)點在中序遍歷下的前驅(qū)結(jié)點；

• 2.1如果前驅(qū)結(jié)點的右孩子為空，將它的右孩子設(shè)置為當(dāng)前結(jié)點，輸出當(dāng)前結(jié)點并把當(dāng)前結(jié)點更新為當(dāng)前結(jié)點的左孩子；
• 2.2如果前驅(qū)結(jié)點的右孩子為當(dāng)前結(jié)點，將它的右孩子重新設(shè)為空，當(dāng)前結(jié)點更新為當(dāng)前結(jié)點的右孩子；

3. 重復(fù)以上步驟 1 和 2，直到當(dāng)前結(jié)點為空。

/*?前序遍歷?*/
void?PreOrderMorris(Node?*?root)
{
????Node?*?cur?=?root;
????Node?*?pre?=?nullptr;

????while?(cur)
????{
????????if?(cur->left?==?nullptr)??//?步驟?1
????????{
????????????cout?<data?<"?";
????????????cur?=?cur->right;
????????}
????????else
????????{
????????????pre?=?cur->left;
????????????while?(pre->right?&&?pre->right?!=?cur)??//?步驟?2，找到?cur?的前驅(qū)結(jié)點
????????????????pre?=?pre->right;

????????????if?(pre->right?==?nullptr)??//?步驟?2.1，cur?未被訪問，將?cur?結(jié)點作為其前驅(qū)結(jié)點的右孩子
????????????{
????????????????cout?<data?<"?";
????????????????pre->right?=?cur;
????????????????cur?=?cur->left;
????????????}
????????????else??//?步驟?2.2，cur?已被訪問，恢復(fù)樹的原有結(jié)構(gòu)，更改?right?指針?
????????????{
????????????????pre->right?=?nullptr;
????????????????cur?=?cur->right;
????????????}
????????}
????}
}

再來看中序遍歷，和前序遍歷相比只改動一句代碼，步驟如下：

1. 如果當(dāng)前結(jié)點的左孩子為空，則輸出當(dāng)前結(jié)點并將其右孩子作為當(dāng)前結(jié)點；
2. 如果當(dāng)前結(jié)點的左孩子不為空，在當(dāng)前結(jié)點的左子樹中找到當(dāng)前結(jié)點在中序遍歷下的前驅(qū)結(jié)點；

• 2.1. 如果前驅(qū)結(jié)點的右孩子為空，將它的右孩子設(shè)置為當(dāng)前結(jié)點，當(dāng)前結(jié)點更新為當(dāng)前結(jié)點的左孩子；
• 2.2. 如果前驅(qū)結(jié)點的右孩子為當(dāng)前結(jié)點，將它的右孩子重新設(shè)為空，輸出當(dāng)前結(jié)點，當(dāng)前結(jié)點更新為當(dāng)前結(jié)點的右孩子；

3. 重復(fù)以上步驟 1 和 2，直到當(dāng)前結(jié)點為空。

/*?中序遍歷?*/
void?InOrderMorris(Node?*?root)
{
????Node?*?cur?=?root;
????Node?*?pre?=?nullptr;

????while?(cur)
????{
????????if?(cur->left?==?nullptr)??//（1）
????????{
????????????cout?<data?<"?";
????????????cur?=?cur->right;
????????}
????????else
????????{
????????????pre?=?cur->left;
????????????while?(pre->right?&&?pre->right?!=?cur)??//（2），找到?cur?的前驅(qū)結(jié)點
????????????????pre?=?pre->right;

????????????if?(pre->right?==?nullptr)??//（2.1），cur?未被訪問，將?cur?結(jié)點作為其前驅(qū)結(jié)點的右孩子
????????????{
????????????????pre->right?=?cur;
????????????????cur?=?cur->left;
????????????}
????????????else??//（2.2），cur?已被訪問，恢復(fù)樹的原有結(jié)構(gòu)，更改?right?指針?
????????????{
????????????????cout?<data?<"?";
????????????????pre->right?=?nullptr;
????????????????cur?=?cur->right;
????????????}
????????}
????}
}

最后看下后序遍歷，后序遍歷有點復(fù)雜，需要建立一個虛假根結(jié)點 dummy，令其左孩子是 root。并且還需要一個子過程，就是倒序輸出某兩個結(jié)點之間路徑上的各個結(jié)點。步驟如下：

1. 如果當(dāng)前結(jié)點的左孩子為空，則將其右孩子作為當(dāng)前結(jié)點；
2. 如果當(dāng)前結(jié)點的左孩子不為空，在當(dāng)前結(jié)點的左子樹中找到當(dāng)前結(jié)點在中序遍歷下的前驅(qū)結(jié)點；

• 2.1. 如果前驅(qū)結(jié)點的右孩子為空，將它的右孩子設(shè)置為當(dāng)前結(jié)點，當(dāng)前結(jié)點更新為當(dāng)前結(jié)點的左孩子；
• 2.2. 如果前驅(qū)結(jié)點的右孩子為當(dāng)前結(jié)點，將它的右孩子重新設(shè)為空，倒序輸出從當(dāng)前結(jié)點的左孩子到該前驅(qū)結(jié)點這條路徑上的所有結(jié)點，當(dāng)前結(jié)點更新為當(dāng)前結(jié)點的右孩子；

3. 重復(fù)以上步驟 1 和 2，直到當(dāng)前結(jié)點為空。

struct?Node
{
????int?data;
????Node?*?left;
????Node?*?right;
????Node(int??data_,?Node?*?left_,?Node?*?right_)
????{
????????data?=?data_;
????????left?=?left_;
????????right?=?right_;
????}
};

void?ReversePrint(Node?*?from,?Node?*?to)
{
????if?(from?==?to)
????{
????????cout?<data?<"?";
????????return;
????}
????ReversePrint(from->right,?to);
????cout?<data?<"?";
}

void??PostOrderMorris(Node?*?root)
{
????Node?*?dummy?=?new?Node(-1,?root,?nullptr);??//?一個虛假根結(jié)點
????Node?*?cur?=?dummy;
????Node?*?pre?=?nullptr;

????while?(cur)
????{
????????if?(cur->left?==?nullptr)??//?步驟?1
????????????cur?=?cur->right;
????????else
????????{
????????????pre?=?cur->left;
????????????while?(pre->right?&&?pre->right?!=?cur)??//?步驟?2，找到?cur?的前驅(qū)結(jié)點
????????????????pre?=?pre->right;

????????????if?(pre->right?==?nullptr)??//?步驟?2.1，cur?未被訪問，將?cur?結(jié)點作為其前驅(qū)結(jié)點的右孩子
????????????{
????????????????pre->right?=?cur;
????????????????cur?=?cur->left;
????????????}
????????????else??//?步驟?2.2，cur?已被訪問，恢復(fù)樹的原有結(jié)構(gòu)，更改?right?指針
????????????{
????????????????pre->right?=?nullptr;
????????????????ReversePrint(cur->left,?pre);
????????????????cur?=?cur->right;
????????????}
????????}
????}
}

dummy 用的非常巧妙，建議讀者配合上面的圖模擬下算法流程。

13 二叉樹前序中序推后序

以上面圖表為例，步驟如下：

1. 根據(jù)前序可知根結(jié)點為1；
2. 根據(jù)中序可知 4 7 2 為根結(jié)點 1 的左子樹和 8 5 9 3 6 為根結(jié)點 1 的右子樹；
3. 遞歸實現(xiàn)，把 4 7 2 當(dāng)做新的一棵樹和 8 5 9 3 6 也當(dāng)做新的一棵樹；
4. 在遞歸的過程中輸出后序。

/*?前序遍歷和中序遍歷結(jié)果以長度為?n?的數(shù)組存儲，pos1?為前序數(shù)組下標(biāo)，pos2?為后序下標(biāo)?*/

int?pre_order_arry[n];
int?in_order_arry[n];

void?PrintPostOrder(int?pos1,?int?pos2,?int?n)
{
????if?(n?==?1)
????{
????????cout?<????????return;
????}
????if?(n?==?0)
????????return;

????int?i?=?0;
????for?(;?pre_order_arry[pos1]?!=?in_order_arry[pos2?+?i];?i++)
????????;

????PrintPostOrder(pos1?+?1,?pos2,?i);
????PrintPostOrder(pos1?+?i?+?1,?pos2?+?i?+?1,?n?-?i?-?1);
????cout?<}

當(dāng)然我們也可以根據(jù)前序和中序構(gòu)造出二叉樹，進(jìn)而求出后序。

/*?該函數(shù)返回二叉樹的根結(jié)點?*/
Node?*?Create(int?pos1,?int?pos2,?int?n)
{
????Node?*?p?=?nullptr;

????for?(int?i?=?0;?i?????{
????????if?(pre_order_arry[pos1]?==?in_order_arry[pos2?+?i])
????????{
????????????p?=?new?Node(pre_order_arry[pos1]);
????????????p->left?=?Create(pos1?+?1,?pos2,?i);
????????????p->right?=?Create(pos1?+?i?+?1,?pos2?+?i?+?1,?n?-?i?-?1);
????????????return?p;
????????}
????}

????return?p;
}

14 判斷二叉樹是不是完全二叉樹

若設(shè)二叉樹的深度為 h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點數(shù)都達(dá)到最大個數(shù)，第 h 層所有的結(jié)點都連續(xù)集中在最左邊，這就是完全二叉樹（Complete Binary Tree）。如下圖：

首先若一個結(jié)點只有右孩子，肯定不是完全二叉樹；其次若只有左孩子或沒有孩子，那么接下來的所有結(jié)點肯定都沒有孩子，否則就不是完全二叉樹，因此設(shè)置 flag 標(biāo)記變量。

bool?IsCBT(Node?*?node)
{
????bool?flag?=?false;
????queue?Q;
????Q.push(node);

????while?(!Q.empty())
????{
????????Node?*?p?=?Q.front();
????????Q.pop();

????????if?(flag)
????????{
????????????if?(p->left?||?p->right)
????????????????return?false;
????????}
????????else
????????{
????????????if?(p->left?&&?p->right)
????????????{
????????????????Q.push(p->left);
????????????????Q.push(p->right);
????????????}
????????????else?if?(p->right)??//?只有右結(jié)點
????????????????return?false;
????????????else?if?(p->left)???//?只有左結(jié)點
????????????{
????????????????Q.push(p->left);
????????????????flag?=?true;
????????????}
????????????else??//?沒有結(jié)點
????????????????flag?=?true;
????????}
????}

????return?true;
}

15 判斷是否是二叉查找樹的后序遍歷結(jié)果

在后續(xù)遍歷得到的序列中，最后一個元素為樹的根結(jié)點。從頭開始掃描這個序列，比根結(jié)點小的元素都應(yīng)該位于序列的左半部分；從第一個大于跟結(jié)點開始到跟結(jié)點前面的一個元素為止，所有元素都應(yīng)該大于跟結(jié)點，因為這部分元素對應(yīng)的是樹的右子樹。根據(jù)這樣的劃分，把序列劃分為左右兩部分，我們遞歸地確認(rèn)序列的左、右兩部分是不是都是二元查找樹。

int?array[n];??//?長度為?n?的序列，注意?begin?和?end?遵循的是左閉右閉原則

bool?IsSequenceOfBST(int?begin,?int?end)
{
????if?(end?-?begin?<=?0)
????????return?true;

????int?root_data?=?array[end];??//?數(shù)組尾元素為根結(jié)點

????int?i?=?begin;
????for?(;?array[i]?????????;

????int?j?=?i;
????for?(;?j?????????if?(array[j]?< root_data)??//?此時右子樹應(yīng)該都大于根結(jié)點；若存在小于，直接?return?false
????????????return?false;

????return?IsSequenceOfBST(begin,?i?-?1)?&&?IsSequenceOfBST(i,?end?-?1);??//?左右子樹是否都滿足
}

16 給定一個二叉查找樹中的結(jié)點（存在一個指向父親結(jié)點的指針），找出在中序遍歷下它的后繼和前驅(qū)

一棵二叉查找樹的中序遍歷序列，正好是升序序列。假如根結(jié)點的父結(jié)點為 nullptr，則：

1. 如果當(dāng)前結(jié)點有右孩子，則后繼結(jié)點為這個右孩子的最左孩子；
2. 如果當(dāng)前結(jié)點沒有右孩子；

• 2.1. 當(dāng)前結(jié)點為根結(jié)點，返回 nullptr；
• 2.2. 當(dāng)前結(jié)點只是個普通結(jié)點，也就是存在父結(jié)點；
• 2.2.1. 當(dāng)前結(jié)點是父親結(jié)點的左孩子，則父親結(jié)點就是后繼結(jié)點；
• 2.2.2. 當(dāng)前結(jié)點是父親結(jié)點的右孩子，沿著父親結(jié)點往上走，直到 n-1 代祖先是 n 代祖先的左孩子，則后繼為 n 代祖先或遍歷到根結(jié)點也沒找到符合的，則當(dāng)前結(jié)點就是中序遍歷的最后一個結(jié)點，返回 nullptr。

/*?求后繼結(jié)點?*/
Node?*?Increment(Node?*?node)
{
????if?(node->right)??//?步驟?1
????{
????????node?=?node->right;
????????while?(node->left)
????????????node?=?node->left;
????????return?node;
????}
????else??//?步驟?2
????{
????????if?(node->parent?==?nullptr)??//?步驟?2.1
????????????return?nullptr;
????????Node?*?p?=?node->parent;??//?步驟?2.2
????????if?(p->left?==?node)??//?步驟?2.2.1
????????????return?p;
????????else??//?步驟?2.2.2
????????{
????????????while?(p->right?==?node)
????????????{
????????????????node?=?p;
????????????????p?=?p->parent;
????????????????if?(p?==?nullptr)
????????????????????return?nullptr;
????????????}
????????????return?p;
????????}
????}
}

仔細(xì)觀察上述代碼，總覺得有點啰嗦。比如，過多的 return，步驟 2 的層次太多。綜合考慮所有情況，改進(jìn)代碼如下：

Node?*?Increment(Node?*?node)
{
????if?(node->right)
????{
????????node?=?node->right;
????????while?(node->left)
????????????node?=?node->left;
????}
????else
????{
????????Node?*?p?=?node->parent;
????????while?(p?&&?p->right?==?node)
????????{
????????????node?=?p;
????????????p?=?p->parent;
????????}
????????node?=?p;
????}

????return?node;
}

上述的代碼是基于結(jié)點有 parent 指針的，若題意要求沒有 parent 呢？網(wǎng)上也有人給出了答案，個人覺得沒有什么價值，有興趣的朋友可以到這里查看。

而求前驅(qū)結(jié)點的話，只需把上述代碼的 left 與 right 互調(diào)即可，很簡單。

17 二分查找樹轉(zhuǎn)化為排序的循環(huán)雙鏈表

二分查找樹的中序遍歷即為升序排列，問題就在于如何在遍歷的時候更改指針的指向。一種簡單的方法時，遍歷二分查找樹，將遍歷的結(jié)果放在一個數(shù)組中，之后再把該數(shù)組轉(zhuǎn)化為雙鏈表。如果題目要求只能使用 O(1)O(1) 內(nèi)存，則只能在遍歷的同時構(gòu)建雙鏈表，即進(jìn)行指針的替換。

我們需要用遞歸的方法來解決，假定每個遞歸調(diào)用都會返回構(gòu)建好的雙鏈表，可把問題分解為左右兩個子樹。由于左右子樹都已經(jīng)是有序的，當(dāng)前結(jié)點作為中間的一個結(jié)點，把左右子樹得到的鏈表連接起來即可。

/*?合并兩個?a,?b?兩個循環(huán)雙向鏈表?*/
Node?*?Append(Node?*?a,?Node?*?b)
{
????if?(a?==?nullptr)?return?b;
????if?(b?==?nullptr)?return?a;

????//?分別得到兩個鏈表的最后一個元素
????Node?*?a_last?=?a->left;
????Node?*?b_last?=?b->left;

????//?將兩個鏈表頭尾相連??
????a_last->right?=?b;
????b->left?=?a_last;

????a->left?=?b_last;
????b_last->right?=?a;

????return?a;
}

/*?遞歸的解決二叉樹轉(zhuǎn)換為雙鏈表?*/
Node?*?TreeToList(Node?*?node)
{
????if?(node?==?nullptr)?return?nullptr;

????//?遞歸解決子樹
????Node?*?left_list?=?TreeToList(node->left);
????Node?*?right_list?=?TreeToList(node->right);

????//?把根結(jié)點轉(zhuǎn)換為一個結(jié)點的雙鏈表，方便后面的鏈表合并??
????node->left?=?node;
????node->right?=?node;

????//?合并之后即為升序排列
????left_list?=?Append(left_list,?node);
????left_list?=?Append(left_list,?right_list);

????return?left_list;
}

18 有序鏈表轉(zhuǎn)化為平衡的二分查找樹（Binary Search Tree）

我們可以采用自頂向下的方法。先找到中間結(jié)點作為根結(jié)點，然后遞歸左右兩部分。所以我們需要先找到中間結(jié)點，對于單鏈表來說，必須要遍歷一邊，可以使用快慢指針加快查找速度。

struct?TreeNode
{
????int?data;
????TreeNode?*?left;
????TreeNode?*?right;
????TreeNode(int?data_)?{?data?=?data_;?left?=?right?=?nullptr;?}
};

struct?ListNode
{
????int?data;
????ListNode?*?next;
????ListNode(int?data_)?{?data?=?data_;?next?=?nullptr;?}
};

TreeNode?*?SortedListToBST(ListNode?*??list_node)
{
????if?(!list_node)?return?nullptr;
????if?(!list_node->next)?return?(new?TreeNode(list_node->data));

????//?用快慢指針找到中間結(jié)點??
????ListNode?*?pre_slow?=?nullptr;??//?記錄慢指針的前一個結(jié)點
????ListNode?*?slow?=?list_node;????//?慢指針
????ListNode?*?fast?=?list_node;????//?快指針
????while?(fast?&&?fast->next)
????{
????????pre_slow?=?slow;
????????slow?=?slow->next;
????????fast?=?fast->next->next;
????}
????TreeNode?*?mid?=?new?TreeNode(slow->data);

????//?分別遞歸左右兩部分
????if?(pre_slow)
????{
????????pre_slow->next?=?nullptr;
????????mid->left?=?SortedListToBST(list_node);
????}
????mid->right?=?SortedListToBST(slow->next);

????return?mid;
}

由 f(n)=2f(\frac n2)+\frac n2f(n)=2f(2n)+2n 得，所以上述算法的時間復(fù)雜度為 O(nlogn)O(nlogn)。

不妨換個思路，采用自底向上的方法：

TreeNode?*?SortedListToBSTRec(ListNode?*&?list,?int?start,?int?end)
{
????if?(start?>?end)?return?nullptr;

????int?mid?=?start?+?(end?-?start)?/?2;
????TreeNode?*?left_child?=?SortedListToBSTRec(list,?start,?mid?-?1);??//?注意此處傳入的是引用
????TreeNode?*?parent?=?new?TreeNode(list->data);
????parent->left?=?left_child;
????list?=?list->next;
????parent->right?=?SortedListToBSTRec(list,?mid?+?1,?end);
????return?parent;
}

TreeNode?*?SortedListToBST(ListNode?*?node)
{
????int?n?=?0;
????ListNode?*?p?=?node;
????while?(p)
????{
????????n++;
????????p?=?p->next;
????}

????return?SortedListToBSTRec(node,?0,?n?-?1);
}

如此，時間復(fù)雜度降為 O(n)O(n)。

19 判斷是否是二叉查找樹

我們假定二叉樹沒有重復(fù)元素，即對于每個結(jié)點，其左右孩子都是嚴(yán)格的小于和大于。

下面給出兩個方法：

方法 1：

bool?IsBST(Node?*?node,?int?min,?int?max)
{
????if?(node?==?nullptr)
????????return?true;
????if?(node->data?<=?min?||?node->data?>=?max)
????????return?false;

????return?IsBST(node->left,?min,?node->data)?&&?IsBST(node->right,?node->data,?max);
}

IsBST(node,?INT_MIN,?INT_MAX);

方法 2：

利用二叉查找樹中序遍歷時元素遞增來判斷。

bool?IsBST(Node?*?node)
{
????static?int?pre?=?INT_MIN;

????if?(node?==?nullptr)
????????return?true;

????if?(!IsBST(node->left))
????????return?false;

????if?(node->data?????????return?false;
????pre?=?node->data;

????return?IsBST(node->right);
}