關于二叉樹的大多數算法題目都是與二叉樹的周遊方式有關的，大都解決方案對二叉樹的周遊改寫即可。下面就主要介紹下二叉樹的常用的四種周遊方式。
其中DFS（Depth-First-Search）的有三種分别為先序周遊，中序周遊及後序周遊，而使用BFS的隻有層序周遊。
一.先序周遊
先序周遊的順序為對于目前結點先通路其本身，再通路其左子樹，最後通路其右子樹。
遞歸實作由于過于簡單就隻給代碼不加描述了，
public static void recurrentSelution(TreeNode root) {
if (root == null) {
return;
}
System.out.print(root.val + " ");
recurrentSelution(root.left);
recurrentSelution(root.right);
}
非遞歸實作大體思路：
需要借助一個堆棧，首先将頭結點入棧。
若堆棧不為空：
從堆棧彈出一個元素進行通路；
若其右孩子存在，則将右孩子入棧；
若其左孩子存在，則将左孩子入棧。
如此即可完成非遞歸的先序周遊。
代碼如下：
public static void nonRecurrentSelution(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode current = stack.pop();
System.out.print(current.val + " ");
if (current.right != null) {
stack.push(current.right);
}
if (current.left != null) {
stack.push(current.left);
}
}
}
二.中序周遊
中序周遊的順序為對于每一個結點先通路左子樹，在通路目前結點，在通路右子樹。對于二叉搜尋樹而言中序周遊的結果即為排序輸入的結果。
遞歸實作代碼：
public static void inOrderRecurr(TreeNode root) {
if (root == null) {
return ;
}
inOrderRecurr(root.left);
System.out.print(root.val + " ");
inOrderRecurr(root.right);
}
非遞歸實作：
首先申請一個堆棧，并令目前結點等于根結點。
若堆棧不為空或目前結點不為空時：
将目前結點及其左孩子以及左孩子的左孩子....依次入棧，直到左孩子為空為止；
從堆棧中彈出一個元素并通路它；
令目前元素等于上一步彈出元素的右孩子。
如此即可完成先序周遊的非遞歸實作
實作代碼如下：
public static void nonInOrderRecurr(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode current = root;
while (current != null || !stack.isEmpty()) {
while (current != null) {
stack.push(current);
current = stack.peek().left;
}
current = stack.pop();
System.out.print(current.val + " ");
current = current.right;
}
}
三.後序周遊
後序周遊的順序為先通路目前結點的左子樹，再通路目前節點的右子樹，最後通路目前結點。
遞歸實作代碼如下：
public static void postOrderRecurr(TreeNode root) {
if (root == null) {
return ;
}
postOrderRecurr(root.left);
postOrderRecurr(root.right);
System.out.print(root.val + " ");
}
非遞歸實作：
細心地小夥伴可能已經發現了，後序周遊的逆序跟先序周遊類似，後序周遊為左，右，中，而先序周遊為中，左，右是以可以對先序周遊的代碼進行稍微的改寫完成中，右，左的周遊順序，然後再将該方式逆序即可。
在先序的非遞歸周遊中，我們是先讓右孩子入棧，再将左孩子入棧的；将其改寫為先讓左孩子入棧，再讓右孩子入棧。同時通路的時候将其先存到另一堆棧，最後将存入新堆棧的元素依次倒入通路即可。
實作代碼如下：
public static void postOrderNonRecurr(TreeNode root) {
Stack<TreeNode> stack1 = new Stack<>();
Stack<TreeNode> stack2 = new Stack<>();
stack1.push(root);
while (!stack1.isEmpty()) {
TreeNode current = stack1.pop();
stack2.push(current);
if (current.left != null) {
stack1.push(current.left);
}
if(current.right != null) {
stack1.push(current.right);
}
}
while(!stack2.isEmpty()) {
System.out.print(stack2.pop().val + " ");
}
}
四.層序周遊
層序周遊，顧名思義一層一層的周遊啊。從上至下，從左至右依次周遊。
層序周遊的非遞歸實作：
首先建立一個隊列，并将頭結點入隊
若隊列不為空時：
從隊列中彈出一個元素，并通路他；
若其左孩子存在則将左孩子入隊；
若其右孩子存在則将右孩子入隊。
如此即可完成對于隊列的層序周遊。
實作代碼如下：
public static void levelOrderTraversal(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode current = queue.remove();
if (current.left != null) {
queue.add(current.left);
}
if (current.right != null) {
queue.add(current.right);
}
System.out.print(current.val + " ");
}
}
對于層序周遊更進一步的要求是在周遊過程中需要輸出換行，使得同一層元素保持的同一行。
對于該問題使用雙指針的方案解決。
初始化時定義另個結點，currentLast和nextLast，分别維持目前層的最後一個結點及下一層的最後一個結點。currentLast = root，nextLast = null。
在通路結點的時候若其等于currentLast時，輸出換行，currentLast = nextLast
在每一個結點入隊時，将nextLast指向入隊結點。這樣就可以保證在通路到目前層最後一個結點時，此時的nextLast指向的是下一層的最後一個結點。
實作代碼如下：
public static void levelOrderTraversal(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
TreeNode last = root;
TreeNode nLast = root.right == null ? root.left : root.right;
queue.add(root);
while (!queue.isEmpty()) {
TreeNode current = queue.remove();
if (current.left != null) {
queue.add(current.left);
nLast = current.left;
}
if (current.right != null) {
queue.add(current.right);
nLast = current.right;
}
System.out.print(current.val + " ");
if (current == last) {
System.out.println();
last = nLast;
}
}
}
![平衡二叉樹詳解筆記[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)