二叉树之中的遍历分为几种情况，前序，中序，后序。在三种顺序之中又有递归和非递归两种。下面就结合一些资料和我自己的总结，将这几种的区别讲清楚。
乍一看这三种遍历方式可能有点糊涂，实际上很好区分，在一棵二叉树之中有根节点和左右子树，左子树必须在右子树之前遍历，那么可以选择的也就是根节点的顺序了。
如果操作顺序是：
根-左-右，那么就是前序遍历
左-根-右，那么就是中序遍历
左-右-根，那么就是后序遍历
也就是根据根节点的遍历顺序不同来区分不同的顺序。
这几种遍历方式都有什么作用呢？下面是作用举例：
前序遍历：输出某个文件夹下面所有文件的名称（可以有子文件夹）。在这种情况下，其子文件夹后面会跟着该子文件夹下面的文件。
中序遍历：中缀表达式变成后缀表达式。中缀表达式是比如 3+4 这种，而后缀表达式是类似于 3 4 + 这种，将表达符号放在最后。
后序遍历：比如统计文件夹的大小。这种情况下一个节点下面的所有子节点被遍历到了才会在最后遍历这个节点。
递归
首先是LeetCode 144 Binary Tree Preorder Traversal,要我们做前序遍历，那么按照我们刚才说的这个思路，就可以得到下面的这个代码：
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> returnInteger = new ArrayList<Integer>();
realLoop(root, returnInteger);
return returnInteger;
}
private void realLoop(TreeNode root, List<Integer> list) {
if (root == null) {
return;
} else {
list.add(root.val);
realLoop(root.left, list);
realLoop(root.right, list);
}
}
}
此处第一个函数是LeetCode官方的解题函数，所以没有改动。实际上结合下面我会给的中序遍历和后序遍历就可以知道，解题思路都是大同小异：
首先，题目自带的函数就是作为main() 函数来使用，只是起到了提供一个外部变量来供真正的循环塞值，和最后返回值的功能。真正的 Loop 里面才是递归的功能。
递归的过程之中，有几个必要的要素：
- 退出条件：在本次的递归之中就是 root == null，即遍历到的节点为null。
- 将任务分解成更小的任务并且使用递归：因为在每次拆分的时候，都自带将树拆分成更小的树的属性，所以这一步是自动做的，不需要任何的多余操作。
下面是中序遍历 94. Binary Tree Inorder Traversal 和 后序遍历145. Binary Tree Postorder Traversal两种的递归算法解答，可见其简直是如出一辙：
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> returnInteger = new ArrayList<Integer>();
realLoop(root,returnInteger);
return returnInteger;
}
private void realLoop(TreeNode root,List<Integer> list){
if(root==null){
return;
}else {
realLoop(root.left, list);
realLoop(root.right, list);
list.add(root.val);
}
}
}
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> returnInteger = new ArrayList<Integer>();
realLoop(root, returnInteger);
return returnInteger;
}
private void realLoop(TreeNode root, List<Integer> list) {
if (root == null) {
return;
} else {
realLoop(root.left, list);
realLoop(root.right, list);
list.add(root.val);
}
}
}
非递归
前序遍历的非递归方式是使用栈来实现。
前序遍历的顺序是根-左-右，思路是：
- 先将根节点入栈
- 出栈一个元素，将右节点和左节点入栈
- 不断重复2步骤2 直至栈空
此处的第二步经过分析如下：
出栈一个元素-意味着其将某个根节点出栈了
将右节点和左节点入栈-先入右节点，再入左节点，其在下一步的出栈过程之中就可以先出左节点，起到了保证左节点在根节点之后，但是在右节点之前的这么一个顺序。
下面是解题代码：
class Solution {
ArrayList<Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
public List<Integer> preorderTraversal(TreeNode root) {
if (root == null) {
return list;
}
stack.push(root);
while (stack.size() != 0) {
realLoop();
}
return list;
}
public void realLoop() {
TreeNode node = stack.pop();
list.add(node.val);
if(node.right!=null){
stack.push(node.right);
}
if(node.left!=null){
stack.push(node.left);
}
}
}
