樹的周遊
近期參加複旦網際網路協會的刷題營，是以我勉勉強強又開始做題啦。現在變得更務實啦，要想提升能力，超過别人就是要依靠一項項的名額的勝利，這樣的評價是更加客觀的。想要提升能力，一方面要靠平時的積累，另外一方面也要依靠瓶頸期的奮力一搏。當然，我的意思是更加側重前者的。話不多說啦，開始今天的話題——樹的周遊。如果用遞歸的方法是非常簡單，也是非常推薦的。但是，用疊代的方法也不難！！！是以我決定在這裡探讨一下。
LeetCode題目
中序周遊 ，前序周遊 和 後序周遊 。當然，我知道有的朋友，就是喜歡野蠻自己的體魄，那你可以試一試，從中序與後序周遊序列構造二叉樹 ， 從前序與中序周遊序列構造二叉樹 以及 根據前序和後序周遊構造二叉樹。 保證你可以受到全身心的虐待。
各種周遊——遞歸實作
有基礎的同學，跳過本節。
首先是TreeNode結構。
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
三種周遊的差別在于，什麼時候通路root的值。下面是中序周遊，傳回按序排序的值。
class Solution {
List<Integer> list = new LinkedList<>();
public List<Integer> inorderTraversal(TreeNode root) {
add(root);
return list;
}
private void add(TreeNode root) {
if (root == null) return;
add(root.left);
list.add(root.val);
add(root.right);
}
}
之後，是前序周遊，先通路root父節點。此後，再通路左子樹。
class Solution {
List<Integer> list = new LinkedList<>();
public List<Integer> inorderTraversal(TreeNode root) {
add(root);
return list;
}
private void add(TreeNode root) {
if (root == null) return;
list.add(root.val);
add(root.left);
add(root.right);
}
}
後序周遊也很簡單，就是最後通路父節點。
class Solution {
List<Integer> list = new LinkedList<>();
public List<Integer> postorderTraversal(TreeNode root) {
add(root);
return list;
}
private void add(TreeNode root) {
if (root == null) return;
add(root.left);
add(root.right);
list.add(root.val);
}
}
各種周遊的原理圖
相信閱讀了上面的内容，大家都産生了一種樹的周遊很簡單的錯覺。然而，真實的情況是确實不難。哈哈，接下來講重點啦！
首先是中序周遊的周遊順序圖。引用LeetCode的說法，Left -> Node -> Right。隻有先通路完左子樹，才能傳回通路中間節點的元素，再通路右子樹。順序按照1，2，3，4，...，7
接下來，大家一定好奇前序周遊的圖。從1開始，到15. 增加箭頭，也許會更加清楚一點，按照LeetCode的說法，Top -> Bottom， Left -> Right。
然後，是後序周遊。同樣是從1開始。加上标線之後，或許更加清楚。按照LeetCode的說法，Bottom -> Top， Left -> Right。
各種周遊——疊代實作
中序周遊
主要通過Stack實作。
前序周遊
還是和之前的代碼一樣,隻不過通路元素的順序變了。
後序周遊
同樣用Stack，但是，List用LinkedList，添加的時候用addFirst方法。
後序周遊，在将中序表達式，轉化為逆波蘭式的時候可以派上用場。
先序周遊，可以在列出目錄中的所有檔案的時候使用——先列出目前檔案夾的所有檔案。
關于各種周遊的用途，參考了這篇文章： https://blog.csdn.net/qq_31929931/article/details/77255658