前言
大家好，我是bigsai，在資料結構與演算法中，二叉樹無論是考研、筆試都是非常高頻的考點內容，在二叉樹中，二叉樹的遍歷又是非常重要的知識點，今天給大家講講二叉樹的層序遍歷，
這部分很多人可能會但是需要注重一下細節，
前面介紹了二叉排序樹的構造和基本方法的實作，遍歷也是比較重要的一環，并且二叉樹的層序遍歷也是bfs的最簡單情況，這里我就將二叉樹的層序遍歷以及常考問題給大家分享一下，
在了解二叉樹的遍歷之前，需要具備資料結構與演算法有佇列、遞回、堆疊、二叉樹，這些內容咱們前面都有講過，有這方面知識欠缺的同學可以往前翻一翻看一看！
層序遍歷
層序遍歷，聽名字也知道是按層遍歷，一個節點有左右節點，按層處理就是當前層兄弟節點的優先級要大于子節點處理的優先級，所以就是要將子節點放到后面處理，這就適合佇列這個資料結構用來存盤，
對于佇列，先進先出，從root節點push到佇列，那么佇列中先出來的順序是第二層的左右(假設都有)，第二層每個節點執行的時候按照左右順序添加到佇列，第三層的節點就會有序的放到最后面……按照這樣的規則就能得到一個層序遍歷的順序，
實作的代碼也很容易理解：
public int[] levelOrder(TreeNode root) {
int arr[]=new int[10000];
int index=0;
Queue<TreeNode>queue=new ArrayDeque<>();
if(root!=null)
queue.add(root);
while (!queue.isEmpty()){
TreeNode node=queue.poll();
arr[index++]= node.val;
if(node.left!=null)
queue.add(node.left);
if(node.right!=null)
queue.add(node.right);
}
return Arrays.copyOf(arr,index);
}
分層存盤
但是在具體筆試他可能要求你分層存盤，例如力扣的102二叉樹的層序遍歷，要求回傳一個List<List<Integer>>型別，
這種相比上面一個多了一層邏輯就是每一層資料放到一塊，這個也很容易，最好想到的就是兩個佇列(容器)一層一層遍歷存盤，然后交替，但是兩個佇列(容器)的寫法常常會被面試官嫌棄，很多面試官讓你想想怎么不用兩個容器實作？
不用雙佇列去列舉結果也很容易，重要的就是先記錄佇列大小size(當前層節點數量)，然后執行size次數的列舉即可，具體代碼為：
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>>list=new ArrayList<List<Integer>>();
if(root==null)return list;
Queue<TreeNode>q1=new ArrayDeque<TreeNode>();
q1.add(root);
while (!q1.isEmpty()) {
int size=q1.size();
List<Integer>value=new ArrayList<Integer>();
for(int i=0;i<size;i++)
{
TreeNode pNode=q1.poll();
if(pNode.left!=null)
q1.add(pNode.left);
if(pNode.right!=null)
q1.add(pNode.right);
value.add(pNode.val);
}
list.add(value);
}
return list;
}
之字形列印
除了這個直接層序遍歷，二叉樹還有很高頻的就是之字形遍歷，例如劍指offer32和力扣103 二叉樹的鋸齒形層序遍歷，它的題目要求為：
請實作一個函式按照之字形順序列印二叉樹，即第一行按照從左到右的順序列印，第二層按照從右到左的順序列印，第三行再按照從左到右的順序列印，其他行以此類推，
這道題雖然不是難題，但是有點繞，本來佇列這玩意我們就要大腦想一下什么順序，又出來一個之字形，屬實增加的思維邏輯，有不少小伙伴反映當時面試官讓手撕這道題，自己以前明明寫過，但是太緊張自己給自己繞進去了！
其實這個問題也很容易轉化，因為值只是存盤，我們按照老樣子去進行層序遍歷，只不過在遍歷時候通過當前層奇偶數來給它判斷是從左往右存盤到結果中還是從右往左放到結果中，當然，判斷奇數偶數也很容易，可以用變數，也可以用結果List的size()都可，
個人實作的一個樸素代碼為：
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> value=new ArrayList<>();//存盤到的最終結果
if(root==null)
return value;
int index=0;//判斷
Queue<TreeNode>queue=new ArrayDeque<>();
queue.add(root);
while (!queue.isEmpty()){
List<Integer>va=new ArrayList<>();//臨時 用于存盤到value中
int len=queue.size();//當前層的數量
for(int i=0;i<len;i++){
TreeNode node=queue.poll();
if(index%2==0)
va.add(node.val);
else
va.add(0,node.val);
if(node.left!=null)
queue.add(node.left);
if(node.right!=null)
queue.add(node.right);
}
value.add(va);
index++;
}
return value;
}
上面實作代碼也僅使用一個佇列，不過這個問題可能有很多更巧妙的解法需要大家自己去挖掘，
結語
二叉樹的層序遍歷是二叉樹內容中較為簡單的內容，但是層序遍歷尤其是之字形遍歷(鋸齒形遍歷)出現的頻率真的太高了，并且最好是掌握比較好的方法不要顯得太臃腫，
不過在實際遇到問題時候，能AC是第一位，然后才是精簡的邏輯和騷氣的代碼，
二叉樹層序遍歷變種問題不多，掌握上面三個問題基本就夠了，而二叉樹的前序、中序、后序遍歷(遞回非遞回)考察非常多，后面會給大家加快梳理總結，敬請期待！
如果文章對你有幫助，歡迎關注我↓，回復【666】免費獲得我自己的原創pdf！ 咱們下次再見！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/300242.html
標籤：其他