引子：五分钟玩转面试考点-数据结构系列，不会像那种严肃、古板的教科书般的博客文章，而是将晦涩难懂的概念和知识点尽可能幽默的细说出来，或结合生活场景，或从零开始分析。带给大家一个严肃而不失风趣的数据结构。
说到二叉树，大家是不是第一个想起来的就是二叉树的遍历？
好吧，不管大家是不是，反正我是...
下面就直接进入正题吧：
首先树的遍历方法有：前序遍历、中序遍历、后序遍历、层级遍历。那这么多遍历方法，他们之间有什么联系？
人之路径，根之输出和二叉树遍历有什么关联？
二叉树的遍历的口诀：
前序遍历：根左右
中序遍历：左根右
后序遍历：左右根
于是，我按照这个口诀，使用递归法和迭代法对二叉树进行了花式遍历。于是就有了自己的一些看法：
- 无论是前、中、后序遍历，其实遍历的路径都是相同的。好像是一个人型，（从根节点出发，一直到二叉树左下位置的节点的左孩子节点(null)此为一撇，然后再遍历其右孩子节点(null)此为一捺）。
- 遍历的区别，在于输出根的时机不同，正如口诀所说：
前序遍历："根左右"就是第一次执行到根节点的时候（此时未遍历孩子节点），输出根；
中序遍历："左根右"就是第二次执行到根节点的时候（此时遍历完左孩子节点），输出根；
后序遍历："根左右"就是第三次执行到根节点的时候（此时遍历完左右孩子节点），输出根；
由此我们可以看出，遍历路径是相同的，输出的都是根节点元素，只不过输出时机不同！！！
ps：什么？你不相信？那好，咱们也写一下代码，看看是否符合口诀~
1. 递归法
1.1 前序遍历
private static ArrayList<Integer> DLRTree(TreeNode root, ArrayList<Integer> list) {
//返回条件是null的情况下，递归出口，原样返回list数组
if (root == null) {
return list;
}
//递归开始【根 左 右】
//递归逻辑
list.add(root.val); //list获取数据
DLRTree(root.left, list); //遍历左子树
DLRTree(root.right, list); //遍历右子树
//递归返回式
return list;
}
心里默念：递归四要素
- 递归出口？
- 递归参数？
- 递归返回值？
- 每次递归的处理逻辑？
- 递归出口：咱们是"人之路径"。一撇在哪里终止？当左子树为null的情况呀。一捺在哪里终止？当发现右子树节点为null的情况下呀。所以root==null为递归出口。
- 递归参数：父节点的左子树节点或者右子树节点。
- 递归返回值 ：ArrayList（引用传递），可以充当返回值。
- 递归处理逻辑：第一次访问到根节点的时候输出根。
我想这个可以把他想成一个元素，是不是好理解些：
image.png
1.2 中序遍历
private static ArrayList<Integer> LDRTree(TreeNode root, ArrayList<Integer> list) {
//返回条件是null的情况下，递归出口，原样返回list数组
if (root == null) {
return list;
}
//递归开始【左 根 右】
//递归逻辑
LDRTree(root.left, list); //遍历左子树
list.add(root.val);
LDRTree(root.right, list); //遍历右子树
//递归返回式
return list;
}
访问完左子树再次访问根节点的时候，输出根。
1.3 后序遍历
private static ArrayList<Integer> LRDTree(TreeNode root, ArrayList<Integer> list) {
//返回条件是null的情况下，递归出口，原样返回list数组
if (root == null) {
return list;
}
//递归开始【左 根 右】
//递归逻辑
LRDTree(root.left, list); //遍历左子树
LRDTree(root.right, list); //遍历右子树
list.add(root.val); //在
//递归返回式
return list;
}
访问完左右子树再次访问根节点的时候，输出根。
2. 迭代法
PS：上面只是热身运动，明白后，咱们看看使用循环怎么遍历二叉树？我猜是使用栈！为啥？因为递归就是栈的思想...
当然，按照人之路径，将节点压栈，此为一撇，直至节点是null，于是我们将节点出栈，找到"人"的连接点，完成一捺。当然如果"捺"上面逻辑复杂，那么还是要走人之路径的。什么时候结束操作？当最右节点完成出栈操作，栈中没有数据。就是程序遍历完毕。
上面说了根之输出，那么第一次访问根时，输出根，为前序遍历。第二次访问根时，输出根，为中序遍历。第三次访问根时，输出根，为后序遍历。
2.1 前序遍历
//栈前序遍历二叉树(后进先出)
public static void stackDLRTree(TreeNode root) {
//借助栈，先序遍历，根 左 右 根在第一次访问时，获取数据
Stack<TreeNode> stack = new Stack<TreeNode>();
while (root != null || !stack.isEmpty()) {
//根打印的时机是 NO.1
while (root != null) {
//第一次访问根节点，输出并放入栈
System.out.println("前序遍历 ： " + root.val);
stack.push(root); //将root节点放到栈中
root = root.left; //指针下移一位
}
if (!stack.isEmpty()) {
root = stack.pop();
root = root.right;
}
}
}
第一次将根压栈的时候，输出根。
2.2 中序遍历
//中序遍历（非递归）
public static void stackLDRTree(TreeNode root) {
//创建栈
Stack<TreeNode> stack = new Stack<TreeNode>();
//打印时机为左节点遍历完毕之后
//栈 Root元素第一个进去，若是出来的话，
while (root != null || !stack.isEmpty()) {
while (root != null) {
//人——“撇”数据开始压栈，直到最 左下 节点（不为null）。
stack.push(root);
root = root.left;
}
//人——“捺”回到再次根节点，准备访问右节点。
//左节点访问完毕，此时，可以访问右节点
root = stack.pop();
System.out.println("中序遍历：" + root.val);
root = root.right; //准备完成 捺，也是按照撇的条件执行
}
}
压栈的时候是第一次操作根节点，那么根节点弹出栈的时候，就是第二次操作根节点。此时输出，便是中序遍历。
2.3 后序遍历
PS：压栈第一次，弹栈第二次。emmm，那后序遍历怎么才是第三次呢？数据都不在栈里面了！
是的，此时一个节点栈已经不能满足我们的需求了，无法三次操作栈中数据，于是我们可以在引入一个计数栈。同步统计根节点被访问的次数。计数栈数据需要和节点栈数据的位置保持一致。
public static void stackLRDTree(TreeNode root) {
//节点栈
Stack<TreeNode> stackNode = new Stack<TreeNode>();
//计数栈
Stack<Integer> stackInt = new Stack<Integer>();
int count = 1; //标志位
//开始一撇
while (root != null || !stackNode.empty()) {
while (root != null) {
//1. root第一次被访问，同步计数栈为0；
stackNode.push(root);
stackInt.push(0);
root = root.left;
}
//栈元素不为null，并且计数栈栈顶元素此时为1，此时是第三次被访问到，
while (!stackNode.empty() && stackInt.peek() == count) {
//计数栈元素移除
stackInt.pop();
//获取遍历元素
System.out.println("后序遍历" + stackNode.pop().val + " ");
}
//准备遍历右节点
if (!stackNode.isEmpty()) {
//2. root被pop时，是第二次被访问到，同步计数栈为1
stackInt.pop();//移除元素0
stackInt.push(1);
//查看栈顶元素(但不移除)回到节点
root = stackNode.peek();
//准备一捺
root = root.right;
}
}
}
3. 层级遍历
层级遍历，其实使用的是队列的数据结构，将父元素输出的时候，将子元素放入队列中。后进后出。
//层级遍历（使用队列）
public static void levelTree(TreeNode root) {
if (root == null) {
return;
}
TreeNode treeNode = null;
//创建队列
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root); //将根节点保存到队列中
//输出数据(队列元素不空的情况下)
while (queue.size() != 0) {
treeNode = queue.poll(); //中间元素，保存信息
System.out.println("层级遍历 ： " + treeNode.val + " ");
if (treeNode.left != null) {
//将指定的元素插入此队列
queue.offer(treeNode.left);
}
if (treeNode.right != null) {
queue.offer(treeNode.right);
}
}
}
层次遍历题目描述.png
上图的描述是将每一层的元素均放到一个集合中，那么如何确定元素位于某一层中？
使用层次遍历时，借助queue队列。每一层进入时，队列中的元素总量便是该层的节点数。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> data = new ArrayList<>();
if(root==null){
return data;
}
java.util.Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (queue.size() != 0) {
//获取该层节点的数量
int count = queue.size();
List<Integer> list = new ArrayList<>();
//小循环，开始遍历该层。
while (count > 0) {
//取出最左边元素
TreeNode node = queue.poll();
//加到list中
list.add(node.val);
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
count--;
}
data.add(list);
}
return data;
}
}
