上一篇文章讲述了树的概念， 特征以及分类， 旨在让我们理解什么是树， 树的一些常用的概念是什么，树的分类有哪些等。如果还对这些不了解， 可以先看上一篇文章大话数据结构之树（一）。同时，上一篇还留了一个小作业，其用意就是让你根据自己的收获，检测一下是否真正理解了。
本篇的主要内容
什么是递归？
如何创建一颗树？
二叉树的遍历
其中二叉树的遍历包含前序， 中序， 后序以及层序遍历，包含递归与常规两种实现方式。
本篇将会以上图为参照， 生成一颗简单的二叉树，并执行遍历操作。
二叉树是如何创建的？
在创建之前， 我们还是要明确两点概念：
-
什么是二叉树？
树是由一个根节点（树根）衍生出的数据结构， 每个节点（叶子节点除外）最多包含两个子节点的树称为二叉树。
树的最小单位是节点
上一篇说过， 树节点的信息包含两部分： 1） 与其他节点的关系 2） 值 。 以上图为例， 一个圆圈代表一个节点， 它有两个元素组成： 与其他节点连接的线以及本身的值A,B,C,D,E,F。
- 树节点的关系
在二叉树中，主要利用的关系有两个： 父亲节点（A）与子节点（BC）， 根据位置分为左孩子节点(B)与右孩子节点（C）。以下分别用父亲和左孩子，右孩子指代。
那么如何创建一颗树呢？
先来实现一个节点， 根据以上关系介绍，节点的内容有4个： 父亲是谁？ 左孩子是谁？ 右孩子是谁？ 值是什么？那么这里我们设定值的类型为String， 用来存储A， B ~ F。如果你想实现一颗树结构，推荐使用泛型。
public class TreeNode {
public TreeNode parent;
public String data;
public TreeNode left;
public TreeNode right;
public TreeNode(String data) {
this.data = data;
}
public TreeNode(TreeNode parent, String data) {
this.parent = parent;
this.data = data;
}
public TreeNode(String data, TreeNode left, TreeNode right) {
this.data = data;
this.left = left;
this.right = right;
}
public TreeNode(TreeNode parent, String data, TreeNode left, TreeNode right) {
this.parent = parent;
this.data = data;
this.left = left;
this.right = right;
}
}
有了树节点，我们来创建一颗树，步骤有两步：
- 创建树节点
- 创建树节点之间的联系
public static TreeNode createTree() {
// 创建根节点A
TreeNode a = new TreeNode("A");
// 创建A的子节点BC， 父节点指向A
TreeNode b = new TreeNode(a, "B");
TreeNode c = new TreeNode(a, "C");
// 创建关系， A的左孩子和右孩子分别是B和C
a.left = b;
a.right = c;
// 创建B的子节点DE， 父节点指向B
TreeNode d = new TreeNode(b, "D");
TreeNode e = new TreeNode(b, "E");
// 创建关系， B的左孩子和右孩子分别是D和E
b.left = d;
b.right = e;
// 创建C的子节点F, 父节点指向C
TreeNode f = new TreeNode(c, "F");
// 创建关系， C的右孩子是F
c.right = f;
return a;
}
通过以上代码， 一颗二叉树就形成了（参照开始图）。如果不明白，可以对着上图和注释理解一下。
树的遍历涉及到递归以及非递归实现， 那么首先肯定是要明白一个概念的，什么是递归？ 如果理解不了递归， 那么递归的实现无疑是无病呻吟； 那么要递归遍历，则要先理解递归； 要理解递归，首先要明白一种数据结构， 那就是栈。那么我们从栈开始说起。
栈Stack
在数据结构系列文章中，有一篇提到了栈，如果不明白栈是什么，可以返回看一下大话数据结构之Vector,Stack。
本文中涉及的递归需要对栈的思想有一个清晰的认识，这样能更好理解递归的概念。
栈是一种后进先出的数据结构。 在日常生活中，有很多这样的现象，如一箱水果，一池水等； 他们的特点是相似的，比如容器的出入口只有一个， 后放入的水果或后流入的水，总是被先拿出来或者先流出来。我们用一个图来表示一下栈结构
在上图的栈中， 只有一个入口与出口。 我们不断把小球放入，分别记为1， 2， 3， 4； 那么取出时，肯定只能是4， 3， 2， 1。 入栈的操作我们常常称之为压栈，即放入了压到栈底了。 在Android中的Activity就是以栈的形式管理的。
递归
明白了栈的原理， 我们再来看递归。 这是一个很绕很难正确理解的概念，很多时候我们觉得懂了，其实不是。
先来看一下递归的定义
程序调用自身的编程技巧称为递归（ recursion）。它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。
以上是递归的官方定义，相信了之后很多人自然而然的进入会懵逼状态。我们来分解一下
程序调用自身称为递归。我们平时喜欢说：以此类推； 什么情况下，才能说以此类推呢？ 比如斐波那契数列： 一个数列，每个数是之前两个数的和，如1， 1， 2， 3， 5， 8， 13... 我们说不完了，OK，以此类推。那么我们来总结以此类推的条件： 1. 我们可以清晰的描述每一次运算（N = N之前两个数的和） 2. 过程很复杂（无限长），我们说不完了。这个以此类推，说的就是“递“的概念； 那么我们平常用，肯定不可能用一个无限大的数，没有尽头。然后考试会让你计算10次计算就行了，也就是只要10次就返回了，这是“归”的概念。
递归的条件有三： 边界条件，前进段和返回段。 那么计算10次就是边界条件，你只要计算10次就行了，不需要让你一直计算下去；在程序中，如果无限循环的一直执行下去，那是一定要崩溃的。 什么是前进段和返回段？ 当我们算了不到10次时，我们需要一直算下去，这就是前进段； 当我们算到10次了，我们不要再算了，这是返回段。
再看斐波那契数列， 让我们算一各斐波那契数列， 简单吗？如果要算第10次的结果，必然要知道第8和9次的结果，直到追溯到第1次和第2次；但是在这个大的计算工程中，我们只需要关注一点， f(n) = f(n - 1) + f(n - 2)就行了，这是核心计算。使用递归，我们就相当于只关注核心的计算，核心的实现， 至于这么大一个工程怎么办， 就让它这么循环下去就行了。当然，实际使用中必须要有边界。
再看递归的定义，调用自身。上面说了，递归只关注核心实现， 像斐波那契数列一样， 因为是要重复的执行 f(n) = f(n - 1) + f(n - 2)。 因为要得到第10次结果f(10), 必然需要f(9), f(8)。f(9)又要得到f8, f7, 知道追根溯源到f1。因此这个过程是重复的，因此要一次次调用自身。
我们总结一下以上的解释，然后再以例子验证。
- 递归是调用自身的过程， 这是用法
- 递归要有边界，这是保证可以执行完毕的前提条件
斐波那契数列说了这么久， 来个例子
public static int febo(int n){
if(n==1){
return 1;
}
if(n==2){
return 1;
}
return febo(n-1)+febo(n-2);
}
结合代码解释一下定义。 假如我们要求第10个斐波那契数， 也就是febo(10)。 我们使用蛮力来算的话， 先从1开始算， 那么就是（大家闪开，我要念经了！）：
第一个是1， 第2个是1， 第3个是2， 第4个3， 第5个是5， 第6个是8 ...
1, 1, 2, 3, 5, 8, 13...
就算是使用for循环来算，也是相当麻烦，用定义来说，这是一个复杂的工程。 然而我们现在只需要调用febo(10)就可以得出结果了， 是不是应了定义那句话： 把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。最后问题小的我们知道核心算法就可以了。这就是递归的好处。
我们再来看febo的实现
return febo(n-1)+febo(n-2);
这是核心算法。我们的定义是什么来着？ 程序调用自身。 再看我们的核心实现，可不就是嘛。
再来分析下实现， 我们是从10开始，不断地递减的，n - 1, n - 2。也就是从10向0靠近。如果我们不加限制， 程序会一直执行下去，崩溃；这显然不是我们想要的，因此我们需要边界，我们的边界是什么呢？ 第一个数是1， 第二个也是1。当n ==1时， 返回1； n == 2时也返回1。我们来分析下三要素：
- 我们从10开始追溯追溯直到2就不调用自身了， 直接返回了。 那么我们边界就是 n > 2吧。
- n > 2时，我们要不断往前求和， 求f(9)~f(3)， 不断前进， 这就是前进段
- n = 2 | n = 1时， 直接返回了，这就是返回段。
注意： 在使用递归时，一定要注意3要素。
通过以上分析， 应该知道递归是什么鬼了。递归就是不断调用自己， 直到一定的条件终止，返回我们想要的结果。递归中实现的是核心的算法实现，它可以把复杂的问题，拆分为细小的问题解决。
以上说了这么多，无非是想让我们明白：
什么是递归？
递归解决什么问题？
递归如何使用？ 注意的问题是什么？
看到这里，希望你们可以停下，自己写一个递归的小例子，这样才能更深刻。
以下通过2个例子来巩固以下，两个例子一个带返回值，一个不带
递归示例1
依次打印从1到10（哇，这个好简单！为了练习递归，请强制使用递归实现）
public static void main(String[] args) {
for(int i = 0; i < 10; i++) {
System.out.println(i);
}
print(0, 10);
}
private static void print(int num, int max) {
if (num > max) {
return;
}
System.out.println(num);
print(++num, max);
}
这是一个很简单的例子。 但不要掉以轻心。虽然我们可以使用循环轻松实现， 但是很多问题足够复杂，是循环解决不了的。print(）方法是我们的核心方法，就是打印。你可以分析一下三要素是什么？ 看看是否真正理解了递归的定义。相对于不断for循环打印， 我们只调用了一次print(0, 10)方法就得到了我们想要的结果。
递归示例2
求第10个斐波那契数
public static int febo(int n){
if(n==1){
return 1;
}
if(n==2){
return 1;
}
return febo(n-1)+febo(n-2);
}
public static void main(String[] args) {
febo(10);
}
上面已经分析过了，不再重复分析。 到这里，很多人奇怪了，递归就递归，你为什么先将栈呢？接下来借着斐波那契数列来讲解一下递归的原理。
递归其实是一个不断压栈的过程。 febo(10)为例的话真心太长，下面以febo(5)为例说明, 以下记为F5
F5 = F4 + F3 = (F3 + F2) + F3 = (F2 + F1) + F2 ) + F3;
1 2 3
这是F5的计算过程，每一次嵌套(每个括号表示一次嵌套)都会把 + 后面的部分压栈，因为按执行顺序，必须先执行 + 前面的部分。上面标注数字的+部分为每次嵌套后压栈的部分， 第一次 + F3不执行， 第二次 + F2不执行， 第三次 + F1不执行。F5的递归计算过程，最后转化为了先计算出F1与F2, 然后是F3, 再然后F4。 + 前面部分都计算出结果后，再从 + F1开始向后计算，知道 + F3。
我们可以看出这个过程， 计算F5的值， F5是最后得到最终值的； 是先计算F1,F2； 根据F1 + F2计算F3; 根据F2 + F3计算F4， 最后才是F5。
理解了栈的原理之后，你会发现，你妈，这和栈的原理是一样的啊，后进先出。F5最先开始调用，却在最后执行； F1是最后调用， 却在最开始执行。
以后会遇到复杂的情况，心里时刻装着一个栈，分析起来会容易很多。
递归的优势是可以轻易的把一个复杂的问题简单化， 转化为最简单最核心的实现。 递归的缺点也很明显， 递归很容易出现问题，所以一定要保证边界的正确性，确保不会出现死循环，一直执行。 其次是递归相对于常规实现来说，资源的消耗高很多，效率低很多。所以想使用递归的你，一定要谨慎。
树的遍历
树的遍历有4种方式，分别是前序遍历， 中序遍历， 后序遍历以及按层遍历； 其中，前中后序的遍历说的是父节点;层序则是按层进行遍历。下图是一个小的满二叉树，以图为例
上面提到，前序，中序，后序是指父节点的优先级。子节点的顺序都是按从左到右。
前序遍历： A（父节点在前） B（左孩子） C（右孩子）
中序遍历： B A C
后序遍历： B C A
层序遍历： A B C
看出问题来了么？ 前序是先遍历父节点， 后序是后遍历父节点，中序则是父节点在中间。层序是按层来遍历的，第一层只有A， 第二层B和C。
小图来说明概念， 这个大图再次拿过来，来解除一些疑惑。
前： A B D E C F
中： D B E A C F
后： D E B F C A
层： A B C D E F
前序解析： 先遍历A ， 然后遍历左子树BDE， 最后遍历右子树CF; 左子树先遍历父节点B ,然后左孩子D，右孩子E； 右子树先遍历C, 然后是右孩子F。 最后的结果： A B D E C F
遍历是从根节点开始，以子树为单位的，而不仅仅是左孩子。最后拼接而成最终遍历结果。以前序分析为例，中序和后序就是上述结果。中序是先遍历左子树， 然后根节点，最后右子树。后序是左子树， 右子树， 根节点。
层遍历则是按层级进行遍历， 第一层A ， 第二层 B C ， 第三层 D E F 。
在面试中，或许会出现给你前中后序任意两个，来还原树的题目，因此在这点上，我们最好可以思考一下这些排序的特点。
前序： 第一个元素必然是根节点
后序： 最后一个元素必然是根节点
层序： 第一个元素必然是根节点
剩下的就是考验你的分析能力了。比如，已经前序和中序，如何推测后序？
- 由前序得， 根节点是A
- 代入根节点A， 得知A的左子树是DBE, 右子树是CF
- 由前序得知，A的左孩子必定是B，（由2知，A有左子树， 那么根据前中后规则， B必然是左孩子）
- 前序B D E得知两种情况， 1） B有左孩子D 右孩子E 2） B无左孩子， 有右子树DE
- 中序D B E得知， B一定有左孩子，因为左中右嘛，没有左孩子不可能存在D B这样的排序
- 根据4 和 5，排序4下的2），得知左子树就是B的左孩子D， 右孩子E
- 由前序得知， C是A的右孩子（A有右子树，所以一定存在根节点）
- 前序CF，中序CF得知， F是C的右孩子（中序F在C之后）
9.得出最终的树
根据上述例子， 大家最好锻炼一下两两组合推测出树是什么样的？ 这样可以加深对树遍历的理解。
树是如何遍历的？ 上面已经讲述的足够清晰， 我们只需要注意一点，就是一定是子树而非单纯的子节点。如前序就是根节点然后左子树右子树。接下来，我们使用代码来实现树的遍历。
递归实现遍历
树的遍历，采用递归实现特别好理解，几乎和定义一致；但是有一个前提，一定要明白什么是递归？还不明白递归的小伙伴建议回上面理解一下递归的定义以及特点。
public static void travelPreOrder(TreeNode root) {
// 前序遍历， 遍历顺序： parent -> left -> child
if (root == null) {
return;
}
System.out.println(root.data);
travelPreOrder(root.left);
travelPreOrder(root.right);
}
public static void travelMidOrder(TreeNode root) {
// 中序遍历， 遍历顺序： left -> parent -> child
if (root == null) {
return;
}
travelMidOrder(root.left);
System.out.println(root.data);
travelMidOrder(root.right);
}
public static void travelPostOrder(TreeNode root) {
// 后序遍历， 遍历顺序： left -> child -> parent
if (root == null) {
return;
}
travelPostOrder(root.left);
travelPostOrder(root.right);
System.out.println(root.data);
}
看到书的遍历的递归实现，是不是眼前一亮！树的遍历从根节点一步步直到所有的叶子节点， 还是蛮复杂的；但是我们知道遍历的规则，因此就有了上述实现，这就是递归 的威力。上述实现为按遍历方式打印树的节点，以trabelPreOrder为例， 就是先遍历根节点（输出root.data）, 然后遍历左子树trabelPreOrder（root.left）也即左孩子的子树；最后是右子树。
递归实现就不做解释了，扫一眼就知道什么意思，前提是真正明白了递归和遍历的原理。下面重点来看非递归的实现方式。
非递归遍历
先来看前序遍历的非递归实现
public static void travelPre(TreeNode root) {
TreeNode parent = root;
Stack<TreeNode> stack = new Stack<>();
while (!stack.isEmpty() || parent != null) {
while (parent != null) {
System.out.println(parent.data);
stack.push(parent);
parent = parent.left;
}
if (!stack.isEmpty()) {
parent = stack.pop();
parent = parent.right;
}
}
}
首先来详细的分析一下，虽然我们已经知道了前序遍历是怎么遍历的；但是代码和根据树写遍历还是不同的。
- 遍历的顺序是左子树， 根， 右子树（记住，一定是子树哦）
- 遍历是从根节点开始的
- 上图的前序遍历是： A B D E C F
- 分析： A B D 是左孩子，左孩子的左孩子... 左孩子穷尽到尽头也即最左的左孩子，也就是D
- 分析： 然后是E， 从最左的左孩子开始，遍历该节点的右子树，从B的右子树E, 到A的右子树C
- 分析： 左子树遍历完毕，开始遍历右子树。（同样的套路）
根据分析来看代码，我们上面说过， 理解递归的最好的方式是栈，后进先出。那么实现自然以栈为存储结构。
while (parent != null) {
System.out.println(parent.data);
stack.push(parent);
parent = parent.left;
}
- 先看分析一（最左侧箭头）：
先是遍历左子树，不断寻找左孩子节点。上述代码的作用是， 先访问根节点（打印）， 然后不断遍历该节点的左子树，直到找到最左左孩子。 上图中的最左侧的箭头， 从A开始，打印A； 然后遍历A的左子树， 即从A的左孩子B开始， parent = parent.left（此时的parent成了B）， 还是先打印B，然后遍历B的左子树， 直到最左的左孩子D，D没有左孩子了。
我们手动分析一下遍历过程
- 遍历根节点A
- A的左子树是BDE, 遍历左子树
- A的左子树的根节点是B，遍历B
- B的左子树是D（虽然只有一个节点）
- 遍历D， D没有左子树， D没有右子树， D子树结束
- 从D向上回溯， B遍历，B左子树遍历，开始遍历右子树E
- 遍历E， E没有左子树，也没有右子树， E子树结束， B的右子树结束， A的左子树结束
- 回溯到A， A遍历完成， A的左子树遍历完成， 遍历A的右子树CF
- 遍历C, C没有左子树， C有右子树F
- 遍历F, F没有左子树，也没有右子树， F子树结束， C子树结束，A的右子树遍历结束
- 整个树的遍历结束
根据上述遍历过程的分析，对比前序遍历的定义，好好的理解一下。 我们理解很深的是： 1）我们遍历的是子树， 而不单单是子节点； 2）右子树的遍历和左子树套路是一样的 3） 先遍历根节点，一路向左找，这样既遍历了根节点ABD, 又遍历了左子树B是A的左子树根节点， D又是B的左子树根节点。然后遍历右子树的过程是从D到B到A的，这是一个从低端回溯的过程。可以看图的箭头， 先从A向下到D， 然后从D向上到A；A的右子树的遍历原理相同。
再来看上面的源码， 从A开始，不断打印根节点；然后parent -> parent.left。 也即一级一级不断指向左孩子A -> B ->D。这段代码结束后，我们的栈中存储的是A B D, 打印的根节点A B D, 当然B相对A来说是左子树，但是在A的左子树中相当于根节点，是相对的。然后我们打印到D了， 根据上面的分析过程， 开始从D回溯到A，打印右子树。看下面的代码
if (!stack.isEmpty()) {
parent = stack.pop();
parent = parent.right;
}
左子树的根节点都入栈了，此时为A B D, 那么开始出栈了。 栈是后进先出的，第一个肯定是D了， 然后开始遍历D的右子树，要结合上面一段代码。D没有右子树，然后出栈的是B， 遍历E的子树了；最后是A的右子树CF。
再来总结一下这个过程，左子树的遍历永远是一个不断向左向下寻找的过程。 A的左子树是BD, 不断向左向下。 B的右子树只有一个E，可能不明显。如果E有一个左孩子G, 那么E的左子树遍历也是不断向左向下寻找的过程。找寻到子树的最左的节点后， 又是一个回溯的过程。比如A - B - D , 然后从D - B - A回溯右子树。这就是典型的栈结构。
平行的向左下的箭头都是找寻左子树的过程。
平行的向右上的箭头都是回溯的过程。
再看代码整体，我们不断通过左子树的压栈，右子树的出栈，最终遍历整个树。到这里，最好结合的分析和代码多想一下，非递归的方式，真的很难理解。
前序遍历讲述的足够详细了， 那么中序就不仔细讲了，因为套路是一样的。先仔细琢磨，多琢磨几遍，理解之后再看中序遍历的源码
public static void travelMiddle(TreeNode root) {
if (root == null) {
return;
}
TreeNode parent = root;
Stack<TreeNode> stack = new Stack<>();
// A B D
while (!stack.isEmpty() || parent != null) {
while (parent != null) {
stack.push(parent);
parent = parent.left;
}
// ABD GH I
// A
// B C
// D E F
// G
// H I
if (!stack.isEmpty()) {
parent = stack.pop();
System.out.println(parent.data);
parent = parent.right;
}
}
}
以上是中序遍历， 代码很相似。我们就要分析一下前序，中序的区别在哪？ 根节点的遍历顺序。 前序遍历时，没加入一个根节点， 就打印了。然后中序呢， 我们要先打印完左子树后， 才能打印根节点。怎么做呢？ 左子树必须遍历完成后，才能打印根节点。 那么 BDE都打印了，才能打印A。 先遍历BDE, 要打印B,必须先打印D吧，有没有什么启发？ 左子树的遍历是从最左孩子开始的。先找，最左孩子，所以入栈操作同前序，找到最左孩子D。因为最左孩子的特点是没有左子树的啊，有的话就不是最左了。所以出栈后打印D， 没有左子树，打印了根节点D, 那么接下来就是D的右子树了，这时parent -> parent.right 指向右子树。D打印完后，回溯到B，回溯到A， 以此类推...
接下来再说后序， 相比于前序中序，后序相对复杂一些，也更难理解一些。我们结合代码来分析一下
public static void travelPost(TreeNode root) {
final boolean isDebug = false;
if (root == null) {
return;
}
TreeNode target = root;
Stack<TreeNode> stack = new Stack<>();
stack.add(target);
while (!stack.isEmpty() || target != null) {
//从指定节点开始， 找到最左子节点（特点：没有左子树）
// 禁止再次压栈 visitCount == 0
while (target != null && target.visitCount == 0) {
target.visitCount = 0;
stack.push(target);
if (isDebug)
System.out.println("++++入栈： " + target.data);
target = target.left;
}
if (!stack.isEmpty()) {
target = stack.lastElement();
if (target.left == null && target.right == null) {
// 没有左右子树，为叶子节点 -> 左（Null） 根（target） 右（Null）
// 叶子节点只访问一次， 等同左右子树遍历结束
target.visitCount = 2;
}
if (target.left == null && target.right != null) {
if (target.visitCount == 0) {
target.visitCount = 1;
}
}
final int visitCount = target.visitCount;
if (visitCount == 1) {
// 1. 左子树遍历结束，开始遍历右子树
target = target.right;
if (isDebug)
System.out.println("^^^^^将要访问： " + target.data);
}
if (visitCount == 2) {
// -> 左右子树都遍历结束，遍历根节点
// 访问根节点
final TreeNode popNode = stack.pop();
System.out.println(popNode.data);
if (isDebug)
System.out.println(">>>>>出栈并访问： " + popNode.data);
if (stack.isEmpty()) {
return;
}
// 回溯
target = stack.peek();
// 一颗子树遍历结束后，回溯的节点访问数 + 1
target.visitCount++;
if (isDebug)
System.out.println("<<<<<回溯到： " + target.data);
}
}
}
}
后序遍历的非递归实现，网上有很多方法。 以上是根据自己的理解不断调试的结果。感觉还是比较好理解。
先来看上图的后序遍历过程
D E B | F C | A
要遍历A，先遍历左子树BDE, 然后遍历右子树CF
遍历是从最左子节点D开始， 那么如何找到D ？ 就是从A到D的寻找算法。上面说过两条线： 一个寻找， 一个回溯。
从A寻找D，寻找线，如果认真看过上面的前中序遍历， 应该很快就想起来，就是那个while循环
找到了D， 然后从D开始回溯直到A。
5.后序遍历中，每个节点是访问两次的，比如B，D子树遍历结束，回溯到B； 然后遍历右子树E， 结束后，还是回到B。访问了两次，第一次是左子树遍历结束； 第二次是右子树遍历结束。有些节点可能没有左子树，或右子树，甚至都没有，如D，其实也是两次。只不过我们直接判断leftChild为空， rightChild为空，省略了而已。
6.那么A的左子树，顺序就是D E B ,其实执行是D -> B -> E -> B
7.以此类推
在分析代码之前，我们先普及两个点：
- 怎么实现第二次经过节点B, 才会访问B呢？ 我们在TreeNode中加入了一个变量visitCount（访问次数）。默认初始是没访问的visitCount = 0; 当左子树遍历完成， 那么visitCount = 1; 右子树遍历完成， 那么visitCount = 2。 也就是说只有当visitCount = 2 并且经过了B节点时，才会遍历B， 此时整棵B的子树就遍历完成了。
2.既然加了visitCount, 那么不同的visitCount代表着什么意义，又需要执行什么操作呢？ 左子树遍历是个神奇的东西。如在A寻找D的过程中， 栈的结构是：A B D。 D就是一棵只有一个节点的子树， B的左子树。D遍历完成后，也同时意味着B的左子树完成了，这时候同时设置B的访问是1。然后再指向B的右子树，遍历E。我们总结一下：
2.1 只有在左子树或右子树遍历完成后， 才会visitCount + 1。
2.2 B的 左子树遍历完成后， visitCount = 1, 此时的动作是切换到B的右孩子E，遍历右子树
2.3 B的右子树遍历完成后， visitCount = 2, 此时的动作是访问根节点B, 然后回溯到A。是的，B这棵子树遍历完成，意味着A的左子树遍历完成了，同时A的visitCount 就是1了。
- 特殊处理。 比如叶子节点D，这种没有左子树，也没有右子树，默认初始化visitCount就是2了。因为没有啊，不需要遍历，相当于已经遍历完了，因此访问的时候直接就访问D了，然后出栈。
理解了上面3条解析，看代码就不会懵逼了。一起看吧
//从指定节点开始， 找到最左子节点（特点：没有左子树）
// 禁止再次压栈 visitCount == 0
while (target != null && target.visitCount == 0) {
target.visitCount = 0;
stack.push(target);
if (isDebug)
System.out.println("++++入栈： " + target.data);
target = target.left;
}
从A开始，不断寻找直到找到D（D没有左孩子）。此时入栈，默认visitCount是0的，也就是初始化值。至于为什么判断==0才能入栈呢？是为了防止重复入栈。大家看， A寻找D时，ABD都入栈了。 D遍历结束后， 回溯到B了，这时候B肯定不能再次入栈了吧，当然也不能出栈，因为还要遍历右子树。
target = stack.lastElement();
if (target.left == null && target.right == null) {
// 没有左右子树，为叶子节点 -> 左（Null） 根（target） 右（Null）
// 叶子节点只访问一次， 等同左右子树遍历结束
target.visitCount = 2;
}
取栈顶元素，栈（ABD）此时栈顶是D，后进先出。看看是不是叶子节点（没有左孩子，也没有右孩子，不孕不育），如果是叶子节点，相当于左右子树遍历都结束了，上面说过，此时visitCount设置为2， 所有的叶子节点都是直接访问的，因为没有子树可以遍历了。上面说过visitCount = 2, 对应的操作就是访问根节点D，然后出栈回溯。
再往下就看到我们的操作了
final int visitCount = target.visitCount;
if (visitCount == 1) {
// 1. 左子树遍历结束，开始遍历右子树
target = target.right;
if (isDebug)
System.out.println("^^^^^将要访问： " + target.data);
}
if (visitCount == 2) {
// -> 左右子树都遍历结束，遍历根节点
// 访问根节点
final TreeNode popNode = stack.pop();
System.out.println(popNode.data);
if (isDebug)
System.out.println(">>>>>出栈并访问： " + popNode.data);
if (stack.isEmpty()) {
return;
}
// 回溯
target = stack.peek();
// 一颗子树遍历结束后，回溯的节点访问数 + 1
target.visitCount++;
if (isDebug)
System.out.println("<<<<<回溯到： " + target.data);
}
上面提到过，VisitCount = 1时，对应的是访问右子树，因为此时左子树遍历结束了。 VisitCount = 2时， 对应的是访问根节点，然后回溯。 右子树是怎么访问的啊？ target指向了右孩子，然后向下执行完了，重新走while(), while的作用说了很多次了，以右孩子为根节点，遍历右子树，这时候肯定又是一个重复的过程了，先从根节点找最左的子节点，然后2，3，4...
VisitCount = 2时，访问根节点了。 怎么访问呢？ 先访问并出栈
final TreeNode popNode = stack.pop();
System.out.println(popNode.data);
仅仅访问出栈还不够啊，访问 + 出栈，说明以target为根节点的子树访问完成了。但是还要继续往上回溯啊，就是接下来的操作，回溯到B， 然后B.VisitCount_++;(D就是B的左子树，D结束了，B的VisitCount当然要+1了，此时就是1了)。 这两个顺带的操作一定要搞清楚， D树的结束，就是B左子树的结束。为什么中间还要一个判断空栈呢？ 想一下，如果最后访问了A，那就结束了啊，不然崩了，A是最后一个栈元素， A都出栈了，你还peek啥。
眼尖的伙计发现了，你中间还有一段是什么鬼？ 兄弟说的是这个吧
if (target.left == null && target.right != null) {
if (target.visitCount == 0) {
target.visitCount = 1;
}
}
前面说，很多人纳闷了，又说过，说的啥？ 叶子节点没有左子树右子树，相当于左右子树遍历结束了，可以直接访问根节点。 那么一个节点没有左子树，只有右子树呢？ 这时当然就相当于左子树遍历完毕了。又有好事的说了，那只有左子树，没有右子树的情况呢？ 乖别闹，我们的操作有右子树遍历和根节点遍历，却没有左子树遍历，因为左子树遍历是顺带的。
没有右子树，毫不影响。
刚开始写后序，一边琢磨一边修改， 耗时良久。 写完之后，总结发现，其实并没有想的那么麻烦。
明确顺序 ， 左子树 -> 右子树 -> 根节点
明确主线： 从A-B-D（寻找）， 从底部开始遍历，逐层向根节点A回溯，直至A的左子树都遍历完成。也即D树遍历，B 树遍历，A树遍历
3.以一棵子树BDE为例， D是叶子节点，直接访问， B的左子树遍历结束， 然后回溯到B跳B的右子树。如果B的右子树不只是E，而是E下面还有子节点。 那么以E为根节点，还是执行以上逻辑，即从E开始寻找最左的子节点， 从最左的子节点开始，执行BDE树的过程。然后一级一级回溯到子树的根节点E。所以，无论是从根节点寻找最左的子节点， 还是左根右的遍历，都是重复的过程。这样思路就分明了
树的遍历是一步步拆分的过程，比如A树（A作为根节点）， 然后拆分为左子树（B树）和右子树（C树）。这时A就是一个独立的顶点。 然后B树和C树为独立的树。 先遍历左子树C树，然后拆分C树，这样一级级拆分到最后，每棵子树只有一个节点，根节点。然后从底部到顶部，从左子树到右子树到根节点，重复的回溯，知道根节点A，结果就出来了。
6.从上面的分析来看源码， 先寻找最左子节点，然后判断特殊情况， 如果visitCount = 1时跟（如B）， 切换到右子树（E）。 之后就是重复上面的过程，以右子树的根节点作为根节点， 再寻找最左子节点。因为栈的后进先出特性，右子树的所有子树遍历完成后， B树的根节点B第二次出栈， 访问B，B可以pop移出栈了。然后指向B的父节点A， 然后继续上面的过程， 结束。
好了，后序遍历解析的足够详细了，如果还不明白，多看几遍，慢慢就明白了（一定要边看边写）。
最难的部分已经过去了，最后解析一下按层遍历的实现。
按层级遍历，是从根节点A出发， 不断保存当前层的子节点，这样一层一层的遍历，直到最后一层。
上图的树，按层遍历流程：
遍历第一层A， 移除第一层A， 保存A的子节点BC（第二层）
遍历第二层BC,移除BC, 保存B和C的子节点 DEF
遍历DEF, 结束
我们看上面的过程，是怎么遍历的？ 遍历第N层， 移除第N层，然后保存N+1层。然后遍历N+1层， 以此类推... 如果仔细看，我们会发现一个规律，那就是保存子节点时， 从按从左右到的顺序，遍历时，也是按该顺序。 先进先出，我们想到了一个数据结构， 队列Queue
public static void travelLevel(TreeNode root) {
if (root == null) return;
Queue<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
while (!queue.isEmpty()) {
final TreeNode node = queue.poll();
if (node != null) {
System.out.println(node.data);
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
}
}
层序遍历很简单，那么简单的来解释一下代码。
A入队列， 此时队列中是A, 第一层
开始
A出队列， 这时队列为空；加入A的子节点BC, 这是第二层，此时队列是BC
B出队列， 这时队列为C； 加入B的子节点DE;队列中有CDE, C为第二层的， DE为第三层。因为C排在队列首位，因此下一次出队列必然是C, C出栈后第二层就遍历完成了。
C出队列，此时队列是DE; 第二层遍历完毕。 然后加入F， 此时队列是DEF, 全是第三层的节点。
D出队列， D没有左右孩子； E出队列，E也没有左右孩子； F出队列， F也没有左右孩子。
遍历完毕。
再看我们的遍历顺序
A 第一层
B C 第二层
D E F 第三层
这就是按层的遍历，每一层是上一层所有节点的所有子节点。
好了，到这里二叉树的遍历就全部结束了。你还有疑问吗？ 如果还不明白，多看几遍；然后还不明白， OK，可以留言给我。
下一篇的内容将是二叉搜索树，又称二叉排序树， 二叉查找树，这是一种很重要的数据结构，二分法的由来便是从这种数据结构衍生而来了。
