二叉樹各種遍歷真的很難？大sai帶你拿捏！
前言
大家好，我是bigsai，好久不見，甚是想念!
今天帶大家征服二叉樹的前中后序遍歷，包含遞歸和非遞歸方式，學到就是賺到!
很多時候我們需要使用非遞歸的方式實現二叉樹的遍歷，非遞歸枚舉相比遞歸方式的難度要高出一些，效率一般會高一些，并且前中后序枚舉的難度呈一個遞增的形式，非遞歸方式的枚舉有人停在非遞歸后序，有人停在非遞歸中序，有人停在非遞歸前序(這就有點拉胯了啊兄弟)。
我們回顧遞歸，它底層其實是維護一個棧，將數據存到棧中，每次拋出棧頂的數據進行處理(也就是遞歸、dfs的方向化、極端化枚舉特征非常明顯)，我們駕馭遞歸的時候更重要的是掌握上下層之間的邏輯關系。
而非遞歸方式我們除了需要掌握上下層的邏輯關系之外，要手動的處理各種條件變更的細節(jié)， 遞歸是一個一來一回的過程，如果我們的邏輯只是在單趟的來或者回中還好，有時候甚至要自己維護來和回的狀態(tài)，所以邏輯上難度還是比較大的。
二叉樹的前序遍歷
二叉樹的前序遍歷是最簡單的，其枚舉方式就是一個最簡單的dfs，學會了二叉樹的前序遍歷，那么后面入門dfs就容易很多。
二叉樹的前序遍歷的枚舉規(guī)則為：根結點 ---> 左子樹 ---> 右子樹，也就是給定一棵樹，輸出操作當前節(jié)點，然后枚舉左子樹(左子樹依然按照根左右的順序進行)，最后枚舉右子樹(右子樹也按照根左右的順序進行)，這樣得到的一個枚舉序列就是二叉樹的前序遍歷序列(也叫先序)。
前序遍歷在二叉樹樹的順序可以看下圖(紅色箭頭指向的表示需要訪問的，可以看出從父節(jié)點枚舉下來第一次就要被訪問)。
在具體實現的方式上，有遞歸方式和非遞歸方式實現。
遞歸
遞歸方式實現的二叉樹前序遍歷很簡單，遞歸我們只需要考慮初始情況、結束邊界、中間正常點邏輯。
初始情況：從root根節(jié)點開始枚舉，函數執(zhí)行傳入root根節(jié)點作為參數。
結束邊界：節(jié)點的左(或右)子節(jié)點為null那么就停止對應節(jié)點的遞歸執(zhí)行。
正常點邏輯：先處理當前點(存儲或輸出)，遞歸調用枚舉左子樹(如果不為null),遞歸調用枚舉右子樹(如果不為null)。
剛好力扣144二叉樹的前序遍歷可以嘗試ac：
- class Solution {
- List<Integer>value=new ArrayList();
- public List<Integer> preorderTraversal(TreeNode root) {
- qianxu(root);
- return value;
- }
- private void qianxu(TreeNode node) {
- if(node==null)
- return;
- value.add(node.val);
- qianxu(node.left);
- qianxu(node.right);
- }
- }
非遞歸
非遞歸的前序還是非常簡單的，前序遍歷的規(guī)則是：根節(jié)點，左節(jié)點，右節(jié)點。但是根左方向一直下去，手動枚舉又沒有遞歸回的過程，一直下去我們怎么找到回來時候的右?guī)c呢?
用棧將路過的節(jié)點先存儲，第一次枚舉節(jié)點輸出儲存然后放入棧中，第二次就是被拋出時候枚舉其右側節(jié)點。
它的規(guī)則大致為：
一直訪問當前節(jié)點并用棧存儲，節(jié)點指向左節(jié)點，直到左孩子為null。
拋出棧頂不訪問。如果有右節(jié)點，訪問其右節(jié)點重復步驟1，如有沒右節(jié)點，繼續(xù)重復步驟2拋出。
這樣的一個邏輯，就會從根出發(fā)一直先往左訪問，訪問結束根、左之后再訪問右節(jié)點(子樹)，得到一個完成的前序遍歷的序列。
具體實現的代碼為：
- class Solution {
- public List<Integer> preorderTraversal(TreeNode root) {
- List<Integer>value=new ArrayList();
- Stack<TreeNode> q1 = new Stack();
- while(!q1.isEmpty()||root!=null)
- {
- while (root!=null) {
- value.add(root.val);
- q1.push(root);
- root=root.left;
- }
- root=q1.pop();//拋出
- root=root.right;//準備訪問其右節(jié)點
- }
- return value;
- }
- }
二叉樹的中序遍歷
二叉樹的中序遍歷出現的頻率還是蠻高的，如果是二叉排序樹相關問題還是蠻多的，你要知道二叉排序樹的中序遍歷是一個有序的序列，如果求二叉排序樹的topk問題，非遞歸中序那效率是非常高的。
中序遍歷在二叉樹樹的順序可以看下圖(紅色箭頭指向的表示需要訪問的，可以看出如果子樹為null，那肯定要訪問，否則就是從左子樹回來的時候才訪問這個節(jié)點)。
遞歸方式
遞歸方式實現很簡單，其邏輯和前序遞歸相似的，力扣94剛好有二叉樹中序遍歷,這里我直接放代碼：
- class Solution {
- public List<Integer> inorderTraversal(TreeNode root) {
- List<Integer>value=new ArrayList<Integer>();
- zhongxu(root,value);
- return value;
- }
- private void zhongxu(TreeNode root, List<Integer> value) {
- if(root==null)
- return;
- zhongxu(root.left, value);
- value.add(root.val);
- zhongxu(root.right, value);
- }
- }
非遞歸方式
非遞歸的中序和前序是非常相似的，前序遍歷的規(guī)則是：根節(jié)點，左節(jié)點，右節(jié)點。中序遍歷的順序是左節(jié)點，根節(jié)點，右節(jié)點 ，在前序中先根后左其實是有點覆蓋的關系(這個左就是下一個跟)，在其非遞歸枚舉實現上我們訪問右節(jié)點時候是先拋出父節(jié)點不訪問，直接訪問父節(jié)點的右節(jié)點，如果拋出父節(jié)點訪問這個父節(jié)點，其實它就是一個中間順序的節(jié)點。
它的規(guī)則大致為：
枚舉當前節(jié)點(不存儲輸出)并用棧存儲，節(jié)點指向左節(jié)點，直到左孩子為null。
拋出棧頂訪問。如果有右節(jié)點，訪問其右節(jié)點重復步驟1，如有沒右節(jié)點，繼續(xù)重復步驟2拋出。
這樣的一個邏輯，就會形成一個中序序列，因為葉子節(jié)點的左右都為null，這樣的規(guī)則依然滿足中序。
實現代碼為：
- class Solution {
- public List<Integer> inorderTraversal(TreeNode root) {
- List<Integer>value=new ArrayList<Integer>();
- Stack<TreeNode> q1 = new Stack();
- while(!q1.isEmpty()||root!=null)
- {
- while (root!=null) {
- q1.push(root);
- root=root.left;
- }
- root=q1.pop();//拋出
- value.add(root.val);
- root=root.right;//準備訪問其右節(jié)點
- }
- return value;
- }
- }
二叉樹的后序遍歷
二叉樹的后序遍歷非遞歸方式實現起來難度最大的，能夠手寫非遞歸后序，一定能亮瞎面試官的眼!
后序遍歷在二叉樹樹的順序可以看下圖(紅色箭頭指向的表示需要訪問的，可以看出如果子樹為null，那肯定要訪問，否則就是從右子樹回來的時候才訪問這個節(jié)點)。
遞歸
二叉樹遞歸方式后序遍歷很簡單，跟前序中序的邏輯一樣，在力扣145有后序的code測試大家可以自己嘗試一下。
這里直接放我寫的后序遞歸方式：
- class Solution {
- List<Integer>value=new ArrayList<>();
- public List<Integer> postorderTraversal(TreeNode root) {
- houxu(root);
- return value;
- }
- private void houxu(TreeNode root) {
- if(root==null)
- return;
- houxu(root.left);
- houxu(root.right);//右子樹回來
- value.add(root.val);
- }
- }
非遞歸
非遞歸的后序就稍微難一點了，大家可以回顧一下二叉樹的前序和中序遍歷，其實都是只用一個棧直接拋出就可以找到右節(jié)點，拋出后棧就空了，但是這個后序遍歷的順序是 左子樹 ---> 右子樹 --->根節(jié)點，也就是處理完右節(jié)點，還要再回到根節(jié)點訪問。所以從邏輯結構上和前序、中序的非遞歸實現方式有一些略有不同。
前序，中序遍歷的順序提取為：
前序: 中入棧—>左入棧—>左孩子入出—>左出棧—>中出棧—>右入棧—>右孩子入出—>右出棧
前序遍歷同一大流程按照入棧順序即形成一個前序序列
中序: 中入棧—>左入棧—>左孩子入出—>左出棧—>中出棧—>右入棧 —>右孩子入出—>右出棧
中序遍歷同一大流程按照出棧順序即形成一個中序序列
但是后序的話應該怎么考慮呢?
其實就是在從左孩子到中準備出棧的時候，先不出棧記成第一次，再將它放入棧中，如果從右孩子返回那么這個節(jié)點就是第三次遍歷(第一次訪問中，然后枚舉左返回第二次，枚舉右返回第三次)，這時候將其拋出就形成一個后序。
如果不理解這里畫了一個簡單的圖幫助理解：
思路理解了，怎么實現呢?最簡單的就是使用一個hashmap存儲節(jié)點訪問次數。
附一下個人實現的代碼：
- class Solution {
- public List<Integer> postorderTraversal(TreeNode root) {
- List<Integer> value=new ArrayList();
- Stack<TreeNode> q1 = new Stack();
- Map<TreeNode,Integer >map=new HashMap<>();
- while(!q1.isEmpty()||root!=null)
- {
- if (root!=null) {
- q1.push(root);
- map.put(root, 1); //t.value標記這個值節(jié)點出現的次數
- root=root.left;
- }
- else {
- root=q1.peek();
- if(map.get(root)==2) {//第二次訪問，拋出
- q1.pop();
- value.add(root.val);
- root=null;//需要往上走
- }
- else {
- map.put(root, 2);
- root=root.right;
- }
- }
- }
- return value;
- }
- }
但是這個情況如果面試官問你如果有hash沖突怎么辦?雖然這種概率非常小幾乎不會但是面試官不會放過你，但是還是要用正統(tǒng)方法來實現。
那么正統(tǒng)方法怎么解決呢?
也很容易，用一個pre節(jié)點一直保存上一次拋出訪問的點，如果當前被拋出的右孩子是pre或者當前節(jié)點右為null，那么就將這個點拋出，否則就將它"回爐重造"一次!
實現代碼為：
- class Solution {
- public List<Integer> postorderTraversal(TreeNode root) {
- TreeNode temp=root;//枚舉的臨時節(jié)點
- List<Integer>value=new ArrayList<>();
- TreeNode pre=null;//前置節(jié)點
- Stack<TreeNode>stack=new Stack<>();
- while (!stack.isEmpty()||temp!=null){
- while(temp!=null){
- stack.push(temp);
- temp=temp.left;
- }
- temp=stack.pop();
- if(temp.right==pre||temp.right==null)//需要彈出
- {
- value.add(temp.val);
- pre=temp;
- temp=null;//需要重新從棧中拋出
- }else{
- stack.push(temp);
- temp=temp.right;
- }
- }
- return value;
- }
- }
是不是覺得非常巧妙?那我再說一種騷操作的代碼，你看 左右中，它反過來就是中右左，這不就是一個反的前序遍歷嘛!所以進行一次反的前序遍歷，然后將結果翻轉一下也能得到這個值啦，當然，你使用雙棧同時翻轉也是一樣的道理!
實現代碼為：
- class Solution {
- public List<Integer> postorderTraversal(TreeNode root) {
- List<Integer>value=new ArrayList();
- Stack<TreeNode> q1 = new Stack();
- while(!q1.isEmpty()||root!=null)
- {
- while (root!=null) {
- value.add(root.val);
- q1.push(root);
- root=root.right;
- }
- root=q1.pop();//拋出
- root=root.left;//準備訪問其右節(jié)點
- }
- Collections.reverse(value);//將結果翻轉
- return value;
- }
- }
給兩個序列如何構造一棵二叉樹
經常會遇到給兩個序列確定一個二叉樹，當然這個序列其中之一必須包含中序遍歷序列。前序、中序確定二叉樹和后序、中序確定一個二叉樹的原理一致。
前序中序確定一棵二叉樹
根據一棵樹的前序遍歷與中序遍歷構造二叉樹。當然也是力扣105的原題。
注意:你可以假設樹中沒有重復的元素。
分析：
給定一個前序序列和一個中序序列，且里面沒有重復的元素，如何構造一棵二叉樹呢?我們可以先單獨觀察兩個序列的特征：
前序遍歷：遍歷規(guī)則為(根，[左側區(qū)域]，[右側區(qū)域])。
中序遍歷：遍歷規(guī)則為([左側區(qū)域]，根，[右側區(qū)域])。
其中前序遍歷的左側區(qū)域和中序遍歷的左側區(qū)域包含元素的范圍相同，根也是相同的。所以可以進行這樣的操作：
根據前序遍歷的第一個找到根節(jié)點，可以確定根。
通過中序遍歷找到根節(jié)點的值，這樣可以知道左側區(qū)域和右側區(qū)域節(jié)點個數多少。
根節(jié)點左側區(qū)域由前中序列確定的左側區(qū)域確定，根節(jié)點的右側節(jié)點由前中序序列的右側區(qū)域確定。
一些操作可以借助這張圖進行理解：
具體的實現上，可以使用一個HashMap存儲中序存儲的序列，避免重復計算。實現的代碼為：
- /**
- * Definition for a binary tree node.
- * public class TreeNode {
- * int val;
- * TreeNode left;
- * TreeNode right;
- * TreeNode(int x) { val = x; }
- * }
- */
- class Solution {
- public TreeNode buildTree(int[] preorder, int[] inorder) {
- if(preorder.length==0)
- return null;
- TreeNode root=new TreeNode(preorder[0]);
- Map<Integer, Integer>map=new HashMap<Integer, Integer>();
- for(int i=0;i<inorder.length;i++)
- {
- map.put(inorder[i], i);
- }
- return buildTree(preorder,0,preorder.length-1, map,0,inorder.length-1);
- }
- private TreeNode buildTree(int[] preorder, int preStart, int preEnd, Map<Integer, Integer> map, int inStart, int inEnd) {
- // TODO Auto-generated method stub
- if(preEnd<preStart||inEnd<inStart)
- return null;
- TreeNode node=new TreeNode(preorder[preStart]);
- int i=map.get(preorder[preStart]);//節(jié)點的值
- int leftlen=i-inStart;//左面的長度
- node.left=buildTree(preorder, preStart+1, preStart+1+leftlen, map, inStart, i-1);
- node.right=buildTree(preorder, preStart+leftlen+1,preEnd, map, i+1, inEnd);
- return node;
- }
- }
中序后序確定一個二叉樹
根據一棵樹的中序遍歷與后序遍歷構造二叉樹，力扣106題
注意:你可以假設樹中沒有重復的元素。
例如，給出
中序遍歷 inorder = [9,3,15,20,7]
后序遍歷 postorder = [9,15,7,20,3]
返回如下的二叉樹：
- 3
- / \
- 9 20
- / \
- 15 7
分析：
有了上面的分析，那么通過一個后序遍歷和中序遍歷去構造一棵二叉樹，其實原理和前面的也是一樣的。
后序遍歷：遍歷規(guī)則為([左側區(qū)域]，[右側區(qū)域]，根)。
中序遍歷：遍歷規(guī)則為([左側區(qū)域]，根，[右側區(qū)域])。
具體實現的代碼為：
- /**
- * Definition for a binary tree node.
- * public class TreeNode {
- * int val;
- * TreeNode left;
- * TreeNode right;
- * TreeNode(int x) { val = x; }
- * }
- */
- class Solution {
- public TreeNode buildTree(int[] inorder,int[] postorder) {
- if(postorder.length==0)
- return null;
- Map<Integer, Integer>map=new HashMap<Integer, Integer>();
- for(int i=0;i<inorder.length;i++)
- {
- map.put(inorder[i], i);
- }
- return buildTree(postorder,0,postorder.length-1, map,0,inorder.length-1);
- }
- private TreeNode buildTree(int[] postorder, int postStart, int postEnd, Map<Integer, Integer> map, int inStart, int inEnd) {
- // TODO Auto-generated method stub
- if(postEnd<postStart||inEnd<inStart)
- return null;
- TreeNode node=new TreeNode(postorder[postEnd]);
- int i=map.get(postorder[postEnd])；
- int leftlen=i-inStart;
- node.left=buildTree(postorder, postStart,postStart+leftlen-1, map, inStart, i-1);
- node.right=buildTree(postorder, postStart+leftlen,postEnd-1, map, i+1, inEnd);
- return node;
- }
- }
結語
好了，今天到這里就先介紹完了，但二叉樹的內容遠不止于此，還有非常牛批的Morris遍歷，以及一些二叉樹騷操作技巧?？紗栴}后面還會慢慢總結分享給大家。
原創(chuàng)不易，如果本文對你有幫助，還請動動小手，幫忙點個贊和在看，分享給好友或者朋友圈，謝謝啦!
