深度閱讀：二叉樹操作詳解-有解無憂

【導讀】：樹是資料結構中的重中之重，尤其以各類二叉樹為學習的難點，在面試環節中，二叉樹也是必考的模塊，本文主要講二叉樹操作的相關知識，梳理面試常考的內容，請大家跟隨小編一起來復習吧，

本篇針對面試中常見的二叉樹操作作個總結：

前序遍歷，中序遍歷，后序遍歷；
層次遍歷；
求樹的結點數；
求樹的葉子數；
求樹的深度；
求二叉樹第k層的結點個數；
判斷兩棵二叉樹是否結構相同；
求二叉樹的鏡像；
求兩個結點的最低公共祖先結點；
求任意兩結點距離；
找出二叉樹中某個結點的所有祖先結點；
不使用遞回和堆疊遍歷二叉樹；
二叉樹前序中序推后序；
判斷二叉樹是不是完全二叉樹；
判斷是否是二叉查找樹的后序遍歷結果；
給定一個二叉查找樹中的結點，找出在中序遍歷下它的后繼和前驅；
二分查找樹轉化為排序的回圈雙鏈表；
有序鏈表轉化為平衡的二分查找樹；
判斷是否是二叉查找樹，

小編推薦一個學C語言/C++的學習裙【 712,284,705】，無論你是大牛還是小白，是想轉行還是想入行都可以來了解一起進步一起學習！裙內有開發工具，很多干貨和技術資料分享！

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

1.1 前序遍歷

對于當前結點，先輸出該結點，然后輸出它的左孩子，最后輸出它的右孩子，以上圖為例，遞回的程序如下：

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

而非遞回版本只是利用 stack 模擬上述程序而已，遞回的程序也就是出入堆疊的程序，

1.2 中序遍歷

對于當前結點，先輸出它的左孩子，然后輸出該結點，最后輸出它的右孩子，以（1.1）圖為例：

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

1.3 后序遍歷

對于當前結點，先輸出它的左孩子，然后輸出它的右孩子，最后輸出該結點，依舊以（1.1）圖為例：

1->2->4->6->7，7 無左孩子，也無右孩子，輸出 7，此時 6 無左孩子，而 6 的右子樹也全部輸出，輸出 6，此時 4 無左子樹，而 4 的右子樹已全部輸出，接著輸出 4，此時 2 的左子樹全部輸出，且 2 無右子樹，輸出 2，此時 1 的左子樹全部輸出，接著轉向右子樹；
3->5，5 無左孩子，也無右孩子，輸出 5，此時 3 的左子樹全部輸出，且 3 無右孩子，輸出 3，此時 1 的右子樹全部輸出，輸出 1，結束，

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

2 層次遍歷

3 求樹的結點數

4 求樹的葉子數

5 求樹的深度

6 求二叉樹第k層的結點個數

7 判斷兩棵二叉樹是否結構相同

不考慮資料內容，結構相同意味著對應的左子樹和對應的右子樹都結構相同，

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 求二叉樹的鏡像

對于每個結點，我們交換它的左右孩子即可，

9 求兩個結點的最低公共祖先結點

最低公共祖先，即 LCA（Lowest Common Ancestor），見下圖：

結點 3 和結點 4 的最近公共祖先是結點 2，即 LCA(3,4)=2，在此，需要注意到當兩個結點在同一棵子樹上的情況，如結點 3 和結點 2 的最近公共祖先為 2，即 LCA(3,2)=2，同理 LCA(5,6)=4，LCA(6,10)=1，

10 求任意兩結點距離

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

如果給定結點 5，則其所有祖先結點為 4,2,1，

12 不使用遞回和堆疊遍歷二叉樹

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

前序，中序，后序遍歷，不管是遞回版本還是非遞回版本，都用到了一個資料結構--堆疊，為何要用堆疊？那是因為其它的方式沒法記錄當前結點的 parent,而如果在每個結點的結構里面加個 parent 分量顯然是不現實的，而線索化正好解決了這個問題，其含義就是利用結點的右孩子空指標，指向該結點在中序序列中的后繼，下面具體來看看如何使用線索化來完成對二叉樹的遍歷，

如果當前結點的左孩子為空，則輸出當前結點并將其右孩子作為當前結點；
如果當前結點的左孩子不為空，在當前結點的左子樹中找到當前結點在中序遍歷下的前驅結點；

2.1如果前驅結點的右孩子為空，將它的右孩子設定為當前結點，輸出當前結點并把當前結點更新為當前結點的左孩子；
2.2如果前驅結點的右孩子為當前結點，將它的右孩子重新設為空，當前結點更新為當前結點的右孩子；

重復以上步驟 1 和 2，直到當前結點為空，

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

如果當前結點的左孩子為空，則輸出當前結點并將其右孩子作為當前結點；
如果當前結點的左孩子不為空，在當前結點的左子樹中找到當前結點在中序遍歷下的前驅結點；

2.1. 如果前驅結點的右孩子為空，將它的右孩子設定為當前結點，當前結點更新為當前結點的左孩子；
2.2. 如果前驅結點的右孩子為當前結點，將它的右孩子重新設為空，輸出當前結點，當前結點更新為當前結點的右孩子；

重復以上步驟 1 和 2，直到當前結點為空，

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

如果當前結點的左孩子為空，則將其右孩子作為當前結點；
如果當前結點的左孩子不為空，在當前結點的左子樹中找到當前結點在中序遍歷下的前驅結點；

2.1. 如果前驅結點的右孩子為空，將它的右孩子設定為當前結點，當前結點更新為當前結點的左孩子；
2.2. 如果前驅結點的右孩子為當前結點，將它的右孩子重新設為空，倒序輸出從當前結點的左孩子到該前驅結點這條路徑上的所有結點，當前結點更新為當前結點的右孩子；

重復以上步驟 1 和 2，直到當前結點為空，

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

13 二叉樹前序中序推后序

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

根據前序可知根結點為1；
根據中序可知 4 7 2 為根結點 1 的左子樹和 8 5 9 3 6 為根結點 1 的右子樹；
遞回實作，把 4 7 2 當做新的一棵樹和 8 5 9 3 6 也當做新的一棵樹；
在遞回的程序中輸出后序，

當然我們也可以根據前序和中序構造出二叉樹，進而求出后序，

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

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

首先若一個結點只有右孩子，肯定不是完全二叉樹；其次若只有左孩子或沒有孩子，那么接下來的所有結點肯定都沒有孩子，否則就不是完全二叉樹，因此設定 flag 標記變數，

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

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

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

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

如果當前結點有右孩子，則后繼結點為這個右孩子的最左孩子；
如果當前結點沒有右孩子；

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