大家好，我是bigsai，在資料結構與算法中，二叉樹無論是考研、筆試都是非常高頻的考點内容，在二叉樹中，二叉樹的周遊又是非常重要的知識點，今天給大家講講二叉樹的層序周遊。
這部分很多人可能會但是需要注重一下細節。
前面介紹了二叉排序樹的構造和基本方法的實作，周遊也是比較重要的一環，并且二叉樹的層序周遊也是bfs的最簡單情況，這裡我就将二叉樹的層序周遊以及常考問題給大家分享一下。
在了解二叉樹的周遊之前，需要具備資料結構與算法有隊列、遞歸、棧、二叉樹，這些内容咱們前面都有講過，有這方面知識欠缺的同學可以往前翻一翻看一看！
層序周遊，聽名字也知道是按層周遊。一個節點有左右節點，按層處理就是目前層兄弟節點的優先級要大于子節點處理的優先級，是以就是要将子節點放到後面處理，這就适合隊列這個資料結構用來存儲。
對于隊列，先進先出。從root節點push到隊列，那麼隊列中先出來的順序是第二層的左右(假設都有)，第二層每個節點執行的時候按照左右順序添加到隊列，第三層的節點就會有序的放到最後面……按照這樣的規則就能得到一個層序周遊的順序。
實作的代碼也很容易了解：
但是在具體筆試他可能要求你分層存儲，例如力扣的102二叉樹的層序周遊，要求傳回一個<code>List<List<Integer>></code>類型。
這種相比上面一個多了一層邏輯就是每一層資料放到一塊，這個也很容易，最好想到的就是兩個隊列(容器)一層一層周遊存儲，然後交替，但是兩個隊列(容器)的寫法常常會被面試官嫌棄，很多面試官讓你想想怎麼不用兩個容器實作？
不用雙隊列去枚舉結果也很容易，重要的就是先記錄隊列大小size(目前層節點數量)，然後執行size次數的枚舉即可，具體代碼為：
除了這個直接層序周遊，二叉樹還有很高頻的就是之字形周遊，例如劍指offer32和力扣103 二叉樹的鋸齒形層序周遊，它的題目要求為：
請實作一個函數按照之字形順序列印二叉樹，即第一行按照從左到右的順序列印，第二層按照從右到左的順序列印，第三行再按照從左到右的順序列印，其他行以此類推。
這道題雖然不是難題，但是有點繞，本來隊列這玩意我們就要大腦想一下什麼順序，又出來一個之字形，屬實增加的思維邏輯，有不少小夥伴反映當時面試官讓手撕這道題，自己以前明明寫過，但是太緊張自己給自己繞進去了！
其實這個問題也很容易轉化，因為值隻是存儲，我們按照老樣子去進行層序周遊，隻不過在周遊時候通過目前層奇偶數來給它判斷是從左往右存儲到結果中還是從右往左放到結果中。當然，判斷奇數偶數也很容易，可以用變量，也可以用結果List的size()都可。
個人實作的一個樸素代碼為：
上面實作代碼也僅使用一個隊列，不過這個問題可能有很多更巧妙的解法需要大家自己去挖掘。
二叉樹的層序周遊是二叉樹内容中較為簡單的内容，但是層序周遊尤其是之字形周遊(鋸齒形周遊)出現的頻率真的太高了，并且最好是掌握比較好的方法不要顯得太臃腫。
不過在實際遇到問題時候，能AC是第一位，然後才是精簡的邏輯和騷氣的代碼。
二叉樹層序周遊變種問題不多，掌握上面三個問題基本就夠了，而二叉樹的前序、中序、後序周遊(遞歸非遞歸)考察非常多，後面會給大家加快梳理總結，敬請期待！
如果文章對你有幫助，歡迎關注我的公衆号，回複【666】免費獲得我自己的原創pdf！ 咱們下次再見！