總結(jié)了19個(gè)常見(jiàn)的二叉樹(shù)操作（附C代碼）

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

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

1.1 前序遍歷

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

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

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

/*?前序遍歷遞歸版?*/
void?PreOrderRec(Node?*?node)
{
????if?(node?==?nullptr)
????????return;
????cout?<data?<"?";???//?先輸出當(dāng)前結(jié)點(diǎn)???
????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é)點(diǎn)??
????????????S.push(node);
????????????node?=?node->left;?????????//?然后輸出左孩子
????????}??????????????????????????????//?while?結(jié)束意味著左孩子已經(jīng)全部輸出

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

1.2 中序遍歷

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

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

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

????InOrderRec(node->left);?????//?先輸出左孩子
????cout?<data?<"?";??//?然后輸出當(dāng)前結(jié)點(diǎn)
????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é)點(diǎn)
????????node?=?S.top()->right;????????//?左孩子全部輸出，當(dāng)前結(jié)點(diǎn)也輸出后，最后輸出右孩子
????????S.pop();
????}
}

1.3 后序遍歷

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

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

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

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

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

/*?后序遍歷非遞歸版?*/
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)?||????????????????????//?第一個(gè)輸出的必是無(wú)左右孩子的葉子結(jié)點(diǎn)，只要第一個(gè)結(jié)點(diǎn)輸出，
????????????(pre &&?(pre == node->left || pre == node->right)))?//?以后的 pre 就不會(huì)是空。此處的判斷語(yǔ)句加入一個(gè) pre，只是用來(lái)
????????{???????????????????????????????????????????????????????//?確保可以正確輸出第一個(gè)結(jié)點(diǎn)。
????????????cout?<data?<"?";??//?左右孩子都全部輸出，再輸出當(dāng)前結(jié)點(diǎn)
????????????pre?=?node;
????????????S.pop();
????????}
????????else
????????{
????????????if?(node->right)
????????????????S.push(node->right);??//?先進(jìn)右孩子，再進(jìn)左孩子，取出來(lái)的才是左孩子
????????????if?(node->left)
????????????????S.push(node->left);
????????}
????}
}

2 層次遍歷

void?LevelOrder(Node?*?node)
{
????Node?*?p?=?node;
????queue?Q;??//?隊(duì)列
????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 求樹(shù)的結(jié)點(diǎn)數(shù)

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

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

4 求樹(shù)的葉子數(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 求樹(shù)的深度

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 求二叉樹(shù)第k層的結(jié)點(diǎn)個(gè)數(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 判斷兩棵二叉樹(shù)是否結(jié)構(gòu)相同

不考慮數(shù)據(jù)內(nèi)容。結(jié)構(gòu)相同意味著對(duì)應(yīng)的左子樹(shù)和對(duì)應(yīng)的右子樹(shù)都結(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 求二叉樹(shù)的鏡像

對(duì)于每個(gè)結(jié)點(diǎn)，我們交換它的左右孩子即可。

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 求兩個(gè)結(jié)點(diǎn)的最低公共祖先結(jié)點(diǎn)

最低公共祖先，即 LCA（Lowest Common Ancestor），見(jiàn)下圖：結(jié)點(diǎn) 3 和結(jié)點(diǎn) 4 的最近公共祖先是結(jié)點(diǎn) 2，即 LCA(3,4)=2。在此，需要注意到當(dāng)兩個(gè)結(jié)點(diǎn)在同一棵子樹(shù)上的情況，如結(jié)點(diǎn) 3 和結(jié)點(diǎn) 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)??//?分別在左右子樹(shù)
????????return?node;

????return?left???left?:?right;??//?都在左子樹(shù)或右子樹(shù)
}

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

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

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

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

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

????return?-1;??//?如果左右子樹(shù)都沒(méi)找到
}

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

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

11 找出二叉樹(shù)中某個(gè)結(jié)點(diǎn)的所有祖先結(jié)點(diǎn)

如果給定結(jié)點(diǎn) 5，則其所有祖先結(jié)點(diǎn)為 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;??//?如果左右子樹(shù)都沒(méi)找到
}

12 不使用遞歸和棧遍歷二叉樹(shù)

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

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

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

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

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

/*?前序遍歷?*/
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é)點(diǎn)
????????????????pre?=?pre->right;

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

再來(lái)看中序遍歷，和前序遍歷相比只改動(dòng)一句代碼，步驟如下：

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

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

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

/*?中序遍歷?*/
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é)點(diǎn)
????????????????pre?=?pre->right;

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

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

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

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

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

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);??//?一個(gè)虛假根結(jié)點(diǎn)
????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é)點(diǎn)
????????????????pre?=?pre->right;

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

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

13 二叉樹(shù)前序中序推后序

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

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

/*?前序遍歷和中序遍歷結(jié)果以長(zhǎng)度為?n?的數(shù)組存儲(chǔ)，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)造出二叉樹(shù)，進(jìn)而求出后序。

/*?該函數(shù)返回二叉樹(shù)的根結(jié)點(diǎn)?*/
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ù)是不是完全二叉樹(shù)

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

首先若一個(gè)結(jié)點(diǎn)只有右孩子，肯定不是完全二叉樹(shù)；其次若只有左孩子或沒(méi)有孩子，那么接下來(lái)的所有結(jié)點(diǎn)肯定都沒(méi)有孩子，否則就不是完全二叉樹(shù)，因此設(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é)點(diǎn)
????????????????return?false;
????????????else?if?(p->left)???//?只有左結(jié)點(diǎn)
????????????{
????????????????Q.push(p->left);
????????????????flag?=?true;
????????????}
????????????else??//?沒(méi)有結(jié)點(diǎn)
????????????????flag?=?true;
????????}
????}

????return?true;
}

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

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

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

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

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

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

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

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

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

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

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

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

/*?求后繼結(jié)點(diǎn)?*/
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ì)觀察上述代碼，總覺(jué)得有點(diǎn)啰嗦。比如，過(guò)多的 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é)點(diǎn)有 parent 指針的，若題意要求沒(méi)有 parent 呢？網(wǎng)上也有人給出了答案，個(gè)人覺(jué)得沒(méi)有什么價(jià)值，有興趣的朋友可以到這里查看。

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

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

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

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

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

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

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

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

????return?a;
}

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

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

????//?把根結(jié)點(diǎn)轉(zhuǎn)換為一個(gè)結(jié)點(diǎn)的雙鏈表，方便后面的鏈表合并??
????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)化為平衡的二分查找樹(shù)（Binary Search Tree）

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

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é)點(diǎn)??
????ListNode?*?pre_slow?=?nullptr;??//?記錄慢指針的前一個(gè)結(jié)點(diǎn)
????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 得，所以上述算法的時(shí)間復(fù)雜度為 O(nlogn)O(nlogn)。

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

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);
}

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

19 判斷是否是二叉查找樹(shù)

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

下面給出兩個(gè)方法：

方法 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：

利用二叉查找樹(shù)中序遍歷時(shí)元素遞增來(lái)判斷。

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);
}