資訊專欄INFORMATION COLUMN
摘要：遞歸解法由于層次遍歷的遞歸解法不是主流，因此只介紹前三種的遞歸解法前序遍歷遞歸遞歸中序遍歷遞歸遞歸后序遍歷遞歸遞歸三種遞歸遍歷的總結遞歸終止的條件為碰到空節點。
目錄
方法一：廣度優先搜索? (以下解釋來自leetcode官方題解)
我們可以用廣度優先搜索解決這個問題。
我們可以想到最樸素的方法是用一個二元組 (node, level) 來表示狀態，它表示某個節點和它所在的層數，每個新進隊列的節點的 level 值都是父親節點的 level 值加一。最后根據每個點的 level 對點進行分類，分類的時候我們可以利用哈希表，維護一個以 level 為鍵，對應節點值組成的數組為值，廣度優先搜索結束以后按鍵 level 從小到大取出所有值，組成答案返回即可。
考慮如何優化空間開銷：如何不用哈希映射，并且只用一個變量 node 表示狀態，實現這個功能呢？
我們可以用一種巧妙的方法修改廣度優先搜索：
>>? 首先根元素入隊
>>? 當隊列不為空的時候,
? ? ? > 求當前隊列的長度 S_i;
? ? ? > 依次從隊列中取 S_i?個元素進行拓展，然后進入下一次迭代.
它和普通廣度優先搜索的區別在于，普通廣度優先搜索每次只取一個元素拓展，而這里每次取 S_i個元素。在上述過程中的第 i?次迭代就得到了二叉樹的第?i 層的?S_i?個元素。
為什么這么做是對的呢？我們觀察這個算法，可以歸納出這樣的循環不變式：第 i 次迭代前，隊列中的所有元素就是第 i 層的所有元素，并且按照從左向右的順序排列。證明它的三條性質（你也可以把它理解成數學歸納法）：
初始化：i=1 的時候，隊列里面只有 root，是唯一的層數為 1 的元素，因為只有一個元素，所以也顯然滿足「從左向右排列」；
保持：如果 i=k 時性質成立，即第 k 輪中出隊 S_k的元素是第 k 層的所有元素，并且順序從左到右。因為對樹進行廣度優先搜索的時候由低 k 層的點拓展出的點一定也只能是 k+1 層的點，并且 k+1 層的點只能由第 k 層的點拓展到，所以由這?S_k?個點能拓展到下一層所有的?S_k+1 ?個點。又因為隊列的先進先出（FIFO）特性，既然第 k 層的點的出隊順序是從左向右，那么第 k+1 層也一定是從左向右。至此，我們已經可以通過數學歸納法證明循環不變式的正確性。
終止：因為該循環不變式是正確的，所以按照這個方法迭代之后每次迭代得到的也就是當前層的層次遍歷結果。至此，我們證明了算法是正確的。
廣度優先搜索的簡化步驟為：
初始化隊列 q，并將根節點 root 加入到隊列中；
當隊列不為空時：
隊列中彈出節點 node，加入到結果中；
如果左子樹非空，左子樹加入隊列；
如果右子樹非空，右子樹加入隊列；
由于題目要求每一層保存在一個子數組中，所以我們額外加入了 level 保存每層的遍歷結果，并使用 for 循環來實現。
看個圖例用以說明：
廣度優先需要用隊列作為輔助結構，我們先將根節點放到隊列中，然后不斷遍歷隊列。
首先拿出根節點，如果左子樹/右子樹不為空，就將他們放入隊列中。第一遍處理完后，根節點已經從隊列中拿走了，而根節點的兩個孩子已放入隊列中了，現在隊列中就有兩個節點 2 和 5。
第二次處理，會將 2 和 5 這兩個節點從隊列中拿走，然后再將 2 和 5 的子節點放入隊列中，現在隊列中就有三個節點 3，4，6。
我們把每層遍歷到的節點都放入到一個結果集中，最后返回這個結果集就可以了。
public List> levelOrder(TreeNode root) { //返回的結果 List> res = new ArrayList>(); if(null == root){ return res; } Queue queue = new LinkedList(); //根節點入隊 queue.add(root); while(!queue.isEmpty()){ //一層的結果 List level = new ArrayList(); int levelCount = queue.size(); //添加節點到一層的List中去 for(int i = 0; i < levelCount ; i ++){ //節點出隊 TreeNode node = queue.remove(); //節點的左子樹入隊 if(node.left != null){ queue.add(node.left); } //節點的右子樹入隊 if(node.right != null){ queue.add(node.right); } level.add(node.val); } res.add(level); } return res; } 用廣度優先處理是很直觀的，可以想象成是一把刀橫著切割了每一層，但是深度優先遍歷就不那么直觀了。
我們開下腦洞，把這個二叉樹的樣子調整一下，擺成一個田字形的樣子。田字形的每一層就對應一個 list。
按照深度優先的處理順序，會先訪問節點 1，再訪問節點 2，接著是節點 3。
之后是第二列的 4 和 5，最后是第三列的 6。
每次遞歸的時候都需要帶一個 index(表示當前的層數)，也就對應那個田字格子中的第幾行，如果當前行對應的 list 不存在，就加入一個空 list 進去。
public List> levelOrder(TreeNode root) { List> res = new ArrayList>(); if(root==null) { return res; } LinkedList queue = new LinkedList(); //將根節點放入隊列中，然后不斷遍歷隊列 queue.add(root); while(queue.size()>0) { //獲取當前隊列的長度，這個長度相當于 當前這一層的節點個數 int size = queue.size(); ArrayList tmp = new ArrayList(); //將隊列中的元素都拿出來(也就是獲取這一層的節點)，放到臨時list中 //如果節點的左/右子樹不為空，也放入隊列中 for(int i=0;i 2.1先輸出當前節點(初始的時候是root節點)
2.2如果左子節點不為空，則遞歸繼續前序遍歷
2.3如果右子節點不為空，則遞歸繼續前序遍歷
3.1如果當前節點的左子節點不為空，則遞歸中序遍歷
3.2輸出當前節點
3.3如果當前節點的右子節點不為空，則遞歸中序遍歷
4.1如果當前節點的左子節點不為空，則遞歸后序遍歷
4.2如果當前節點的右子節點不為空，則遞歸后序遍歷
4.3輸出當前節點
如果你按照 根節點 -> 左孩子 -> 右孩子 的方式遍歷，即「先序遍歷」，每次先遍歷根節點，遍歷結果為 1 2 4 5 3 6 7；
同理，如果你按照 左孩子 -> 根節點 -> 右孩子 的方式遍歷，即「中序序遍歷」，遍歷結果為 4 2 5 1 6 3 7；
如果你按照 左孩子 -> 右孩子 -> 根節點 的方式遍歷，即「后序序遍歷」，遍歷結果為 4 5 2 6 7 3 1；
最后，層序遍歷就是按照每一層從左向右的方式進行遍歷，遍歷結果為 1 2 3 4 5 6 7。
由于層次遍歷的遞歸解法不是主流，因此只介紹前三種的遞歸解法
public List preorderTraversal(TreeNode root) { //遞歸 List list = new ArrayList<>(); preOrder(root,list); return list; } public void preOrder(TreeNode root,List list){ if(root == null){ return; } list.add(root.val); preOrder(root.left,list); preOrder(root.right,list);} public List inorderTraversal(TreeNode root) { //遞歸 List list = new LinkedList<>(); inOrder(root,list); return list; } public void inOrder(TreeNode root,List list){ if(root == null){ return; } inOrder(root.left,list); list.add(root.val); inOrder(root.right,list);} public List postorderTraversal(TreeNode root) { //遞歸 List list = new LinkedList<>(); postOrder(root,list); return list; } public void postOrder(TreeNode root,List list){ if(root == null){ return; } postOrder(root.left,list); postOrder(root.right,list); list.add(root.val);} 核心思想：
1.每拿到一個節點就把它保存在棧中
2.繼續對這個節點的左子樹重復過程1，直到左子樹為空
3.因為保存在棧中的節點都遍歷了左子樹但是沒有遍歷右子樹，所以對棧中節點出棧并對它的右子樹重復過程1
4.直到遍歷完所有節點
public List preorderTraversal(TreeNode root) { //迭代 List list = new ArrayList<>(); if(root == null){ return list; } Deque stack = new LinkedList(); //臨時節點，幫助遍歷二叉樹 TreeNode node = root; //棧的作用是用來短暫的保存遍歷節點的值，以助于最后值的返回 while(!stack.isEmpty() || node != null){ while(node != null){ list.add(node.val); stack.push(node); node = node.left; } node = stack.pop(); node = node.right; } return list;} public List inorderTraversal(TreeNode root) { //迭代 List list = new ArrayList<>(); if(root == null){ return list; } Deque stack = new LinkedList<>(); while(!stack.isEmpty() || root != null){ while(root != null){ stack.push(root); root = root.left; } root = stack.pop(); list.add(root.val);//出棧的時候才將父節點?的值加入到結果中 root = root.right; } return list;} 和前序遍歷的代碼完全相同，只是在出棧的時候才將父節點?的值加入到結果中。
public List postorderTraversal(TreeNode root) { LinkedList list = new LinkedList<>(); Stack stack = new Stack<>(); while (root != null || !stack.isEmpty()) { if (root != null) { stack.push(root); list.addFirst(root.val);//addFirst():向鏈表首部添加元素 root = root.right; } else { root = stack.pop(); root = root.left; } } return list;} 前序遍歷和后序遍歷之間的關系：
前序遍歷順序為：根 -> 左 -> 右
后序遍歷順序為：左 -> 右 -> 根
如果1： 將前序遍歷中節點插入結果鏈表尾部的邏輯，修改為將節點插入結果鏈表的頭部
那么結果鏈表就變為了：右 -> 左 -> 根
如果2： 將遍歷的順序由從左到右修改為從右到左，配合如果1
那么結果鏈表就變為了：左 -> 右 -> 根
這剛好是后序遍歷的順序
基于這兩個思路，想一下如何處理：
修改前序遍歷代碼中，節點寫入結果鏈表的代碼，將插入隊尾修改為插入隊首
修改前序遍歷代碼中，每次先查看左節點再查看右節點的邏輯，變為先查看右節點再查看左節點
前序遍歷和中序遍歷之間的關系：
和前序遍歷的代碼完全相同，只是在出棧的時候才將父節點的值加入到結果中。
遍歷特點：Morris 遍歷利用了樹中大量空閑指針的特性
當前節點cur,一開始cur來到整樹頭
1）cur無左樹，cur? = cur.right（cur右移）
2）cur有左樹，找到左樹最右節點，mostright；此時我們又可以分為兩種情況，一種是葉子節點添加 right 指針的情況，一種是去除葉子節點 right 指針的情況
?A.mostright 的右指針指向null的mostright.right = cur,? cur = cur.left（cur左移）
?B.mostright 的右指針指向cur的mostright.right = null(為了防止重復執行，則需要去掉 right 指針),? ????cur = cur.right（cur右移）
當cur == null時，整個過程結束。
遍歷特點：有左樹節點必遍歷到兩次，沒有左樹的節點必遍歷到一次
public static void morris(Node head){ if(head == null){ return; } Node cur = head; Node mostRight = null; while(cur != null){ //cur有沒有左樹 mostRight = cur.left; if(mostRight != null){//有左樹的情況 //找到cur左樹上，真實的最右節點 //前者說明是第一次來到當前的cur，后者說明是第二次來到當前的cur while(mostRight.right != null && mostRight.right != cur){ mostRight = mostRight.right; } //從while中出來，mostRight一定是cur左樹上的最右節點 if(mostRight.right == null){ mostRight.right = cur; cur = cur.left; continue;//結束的是外層的循環！！！！！！！！！！！！！ }else{//走到這里意味著：mostRight.right == cur mostRight.right = null; } } //cur沒有左樹 cur = cur.right; }}空間復雜度：利用空閑的指針，使用了兩個變量完成了遍歷，空間復雜度是常數級別的
時間復雜度：?
第一次來到一個節點，就打印；第二次來到這個節點，不打印
public static void morrisPre(Node head){ if(head == null){ return; } Node cur = head; Node mostRight = null; while(cur != null){ mostRight = cur.left; if(mostRight != null){ while(mostRight.right != null && mostRight.right != cur){ mostRight = mostRight.right; } if(mostRight.right == null){ mostRight.right = cur; System.out.print(cur.value + " "); cur = cur.left; continue; }else{ mostRight.right = null; } }else{ System.out.print(cur.value + " "); } cur = cur.right; } System.out.println();}對于能回到自己兩次的節點，第二次時打印，對于只能來到自己一次的節點，直接打印
只要一個節點要往右移動，就打印
public static void morrisIn(Node head){ if(head == null){ return; } Node cur = head; Node mostRight = null; while(cur != null){ mostRight = cur.left; if(mostRight != null){ while(mostRight.right != null && mostRight.right != cur){ mostRight = mostRight.right; } if(mostRight.right == null){ mostRight.right = cur; cur = cur.left; continue; }else{ mostRight.right = null; } } System.out.print(cur.value + " "); cur = cur.right; } System.out.println();}public static void morrisPos(Node head) { if(head == null) { return; } Node cur = head; Node mostRight = null; while(cur != null) { mostRight = cur.left; if(mostRight != null) { while(mostRight.right != null && mostRight.right != cur) { mostRight = mostRight.right; } if(mostRight.right == null) { mostRight.right = cur; cur = cur.left; continue; }else { mostRight.right = null; printEdge(cur.left);//逆序打印左樹的右邊界 } } cur = cur.right; } printEdge(head);//最后打印整棵樹的右邊界 System.out.println(); } public static void printEdge(Node head) { Node tail = reverseEdge(head); Node cur = tail; while(cur != null) { System.out.print(cur.value + " "); cur = cur.right; } reverseEdge(tail); } private static Node reverseEdge(Node from) { Node pre = null; Node next = null; while(from != null) { next = from.right; from.right = pre; pre = from; from = next; } return pre; }Morris后序遍歷比較復雜，可以看看相關的視頻講解--左神算法系列。
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/123503.html
摘要：當集合為空時，稱該二叉樹為空二叉樹。也就是說，如果一個二叉樹的層數為，且結點總數是，則它就是滿二叉樹。完全二叉樹完全二叉樹是效率很高的數據結構，完全二叉樹是由滿二叉樹而引出來的。 ...
摘要：代碼實現如下二叉樹的創建與銷毀二叉樹的創建問題通過前序遍歷的數組給定一串字符串，代表的是空樹，其他的都是節點。 ??本篇博客我要來和大家一起聊一聊數據結構中的二...
閱讀 3723·2021-11-24 09:39
閱讀 1869·2021-11-16 11:45
閱讀 616·2021-11-16 11:45
閱讀 1028·2021-10-11 10:58
閱讀 2475·2021-09-09 11:51
閱讀 1940·2019-08-30 15:54
閱讀 687·2019-08-29 13:13
閱讀 3465·2019-08-26 12:18
