摘要
關于二叉樹的周遊也是很常見的問題，而最常用的周遊也是标題中的說的四種方式。
先序，中序和後序可以采用遞歸和疊代的方式來完成，也是深度優先的思想，後面會寫出遞歸和疊代的方法。
層級周遊主要是借用隊列這種資料結構來進行對二叉樹逐層周遊，是廣度優先的思想。
現在我們來寫一下每一種的周遊方法。
1.中序周遊
先說一下中序周遊的方式是什麼。對于二叉樹的每個節點，從根節點開始，都要先周遊目前節點的左子節點，再周遊目前節點，然後是目前節點的右子節點。
簡單來說就是左子樹 -> 根節點 -> 右子樹。
遞歸的方法很簡單，這裡面我們不詳細的去說，直接上代碼。
const logSort1 = function (arr, node) {
if (node != null) {
logSort1(arr, node.left)
arr.push(node.val)
logSort1(arr, node.right)
}
}
如果我們想用疊代的方法來做，就必須要有一個棧，因為遞歸的本質上其實維護了一個内部的棧，是以我們想要用循環的方式也需要自己建立一個棧。
第一步：
由于周遊的方式是先左子樹，是以我們可以從根節點到下面的每個左子節點，一直入棧。
第二步：
出棧，出棧的時候，我們可以将出棧的節點放到結果集中了，然後拿到出棧節點的右子節點，以這個右子節點為根節點重複第一步。下圖是2這個節點出棧後的情況，後序的情況可以自己繼續推。
第三步：
直到棧已經空了并且出棧的最後一個節點已經沒有右子節點了，我們可以說周遊已經結束了。
2.先序周遊
先序周遊的方式，對于二叉樹的所有節點，是先周遊目前節點，再周遊目前節點的左子節點，最後再周遊目前節點的右子節點。
總結來說：根節點 -> 左子樹 -> 右子樹
同樣，遞歸的方式我們不多說，直接上代碼。
const logSort3 = function (arr, node) {
if (node != null) {
arr.push(node.val);
logSort3(arr, node.left);
logSort3(arr, node.right);
}
}
我們主要來說一下疊代的方式，同樣的，隻要我們用循環不用遞歸，那麼我們必須要先維護一個自己的棧。
第一步：
由于是先根節點，再左子節點，我們依舊從根節點，依次到每個左子節點進行入棧，不過，記住剛才中序是在出棧的時候入結果集，但是這次我們根節點的優先級大于左子節點，是以我們入棧的時候就要把節點入結果集。
第二步：
出棧，這次我們出棧的節點我們不入結果集裡面，但是我門出棧節點的右子節點，要重複第一步，下圖是2節點出棧的情況。
第三步：
直到棧為空并且最後出棧的節點不包含右子節點，我們才能認為周遊已經結束。
const logSort4 = function (root) {
let stack = [], res = [];
while (stack.length > 0 || root) {
while (root != null) {
res.push(root.val)
stack.push(root)
root = root.left;
}
let node = stack.pop();
root = node.right
}
return res;
}
3.後序周遊
後序周遊的情況就是，對于二叉樹的所有節點，先周遊目前節點的左子節點，然後是目前節點，最後是目前節點的右子節點。
總結來說：左子樹 -> 根節點 -> 右子樹
遞歸的方法直接上代碼，重點還是在疊代的方法：
const logSort5 = function (arr, node) {
if (node != null) {
logSort5(arr, node.left);
logSort5(arr, node.right);
arr.push(node.val);
}
}
有了前兩種周遊的講解，我們一定知道我們首先要維護一個棧了，那麼後序周遊的情況我們要怎麼用循環來解決呢？
第一步：
我們一定要記住優先級，這種周遊方式的優先級就是left > right > root。
既然左子樹的優先級最高，我們依舊從根節點，到每個左子節點進行入棧，由于根節點的優先級最低，是以我們不能在入棧的時候進行入結果集的操作。
第二步：
出棧的情況有點複雜，我們想一下：
如果出棧節點沒有右子節點（不考慮左子節點的情況，因為是以左子節點入棧），或者右子節點已經入了結果集。那麼是不是就能說明出棧節點已經變成了優先級最高的情況（或者說是一個不存在左右節點的根節點），這個時候我們就可以将該節點入結果集。
如果出棧節點有右子節點，那麼說明出棧節點的優先級一定沒有右子節點高，那麼我們隻能禁止這個出棧節點出棧，并且将優先級比他高的右子節點入棧，并且要以這個右子節點去重複第一步。
這裡有一點難以了解，但隻要記住優先級的順序，并且記住我是以左子節點的順序入棧的，就是可以想通的。
下圖是2節點要出棧的情況，沒出去憋回去了哈。
第三步：
直到這個棧已經為空并且出棧的節點沒有右子節點了，我們可以說周遊已經結束了。
const logSort6 = function (root) {
let stack = [], res = [], pre = null
while (stack.length > 0 || root) {
while (root != null) {
stack.push(root)
root = root.left;
}
root = stack.pop();
if (root.right === null || pre === root.right) {
res.push(root.val)
pre = root;
root = null
} else {
stack.push(root)
root = root.right
}
}
return res
}
4.層級周遊
關于層級周遊，也是通過隊列這種資料結構，先進先出，通過廣度優先的方式來實作的。
第一步： 我們首先将根節點放入隊列中。
第二步：我們将隊列的節點全部出隊列，入結果集，并且每個節點出隊列的時候，都将該節點的左子節點和右子節點入隊列。
第三步：重複第二步，直到隊列已經為空，我們可以說周遊已經結束了。
這裡面注意一下，我們層級周遊可以記錄層數的奧。
const logSort7 = function (root) {
let queue = [root], res = [];
while (queue.length > 0) {
let len = queue.length;
let arr = [];
for (var i = 0; i < len; i++) {
let node = queue.shift();
arr.push(node.val)
if (node.left) {
queue.push(node.left)
}
if (node.right) {
queue.push(node.right)
}
}
res.push(arr)
}
return res
}