二叉樹各種遍歷真的很難?大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)不易,如果本文對你有幫助,還請動動小手,幫忙點個贊和在看,分享給好友或者朋友圈,謝謝啦!