这两天在做二叉树相关的算法题，做一点学习笔记。（连二叉树都不会？确实不熟练，平时工作也没有要去写二叉树相关的算法或者数据结构的场景。因为自己菜，所以更加要努力学！）
定义
先看下维基百科的解释：在计算机科学中，二叉树（英语：binary tree）是每个节点最多只有两个分支（即不存在分支度大于2的节点）的树结构。通常分支被称作“左子树”或“右子树”。二叉树的分支具有左右次序，不能随意颠倒。
由于二叉树本身定义的特点，具有高度的局部重复性，所以在深度优先遍历二叉树时，通常采用递归的方式去实现，这样实现出来的代码非常简洁漂亮，也比较容易看懂。
深度优先遍历
一般我们深度优先遍历二叉树有三种最常见的顺序遍历：前序、中序、后序。
前序的遍历顺序为：访问根结点 -> 遍历左子树 -> 遍历右子树
中序的遍历顺序为：遍历左子树 -> 访问根结点 -> 遍历右子树
后序的遍历顺序为：遍历左子树 -> 遍历右子树 -> 访问根结点
注意这里的左右是整个子树，而不是一个结点，因为我们需要遍历整棵树，所以每次遍历都是按照这个顺序去执行，直到叶子结点。
举个例子，假如有如下二叉树：
前序遍历得到的序列就是 a - b - c - d - e
中序遍历得到的序列就是 b - a - d - c - e
后序遍历得到的序列就是 b - d - e - c - a
思路我们就用前序遍历来讲（非常不建议去人肉递归，至少我的脑子吃不消三层。。。）：
第一层递归：
先访问根结点，所以输出根结点 a，然后遍历左子树（l1），再遍历右子树（r1）；
第二层递归：
对于 l1，先访问根结点，所以输出此时的根结点 b，然后发现 b 的左右子树为空，结束递归；
对于 r1，先访问根结点，所以输出此时的根结点 c，然后遍历左子树（l2），再遍历右子树（r2）；
第三层递归：
对于 l2，先访问根结点，所以输出此时的根结点 d，然后发现 d 的左右子树为空，结束递归；
对于 r2，先访问根结点，所以输出此时的根结点 e，然后发现 e 的左右子树为空，结束递归；
前中后序特征
根据前中后序的定义，其实我们不难发现有如下特征：
• 前序的第一个一定是 root 节点，后序的最后一个一定是 root 节点
• 每种排序的左子树和右子树分布都是有规律的
• 对于每一个子树都遵循上面两个规律的树
这些特征也就是定义中对顺序的表现。
各种推导
这边列举一下对于二叉树的遍历最基本的几个算法题：
• 给定二叉树得出其前/中/后序遍历的序列；
• 根据前序和中序推导后序（或者推导整颗二叉树）；
• 根据后序和中序推导前序（或者推导整颗二叉树）；
对于二叉树的遍历，前面也讲过，通常采用递归来做，对于递归，有模版可以直接套用：
public void recur(int level, int param) { // terminator if (level > max_level) { // process result return; } // process current logic process(level, param); // drill down recur(level+1, newparam); // restore current status}
这个是我这两天看极客时间的算法训练营中超哥（覃超）讲到的比较实用的小技巧（这个模版对于新手特别好），遵循上面的三步骤（如果有局部变量需要释放或者额外处理则第四步去做）能比较有条理的写出递归代码。
这里拿根据前序和中序推导后序来举例：
先初始化两个序列：
int[] presequence = {1, 2, 3, 4, 5, 6, 7, 8, 9};int[] insequence = {2, 3, 1, 6, 7, 8, 5, 9, 4};
通过上面说到的几个特征，我们已经可以找到最小重复子问题了，每次递归
根据前序的第一个结点值去匹配中序中该结点值所在的索引 i，这样我们就能得到索引 i 的前后两部份分别对应左右子树，接着分别去遍历这两个左右子树，然后输出当前前序的第一个结点值，也就是根结点。
根据自顶向下的程序设计方法，我们可以先写出如下初始递归调用：
list<integer> result = new arraylist<>();preandintopost(0, 0, presequence.length, presequence, insequence, result);
第一个参数表示前序序列的第一个元素索引；
第二个参数表示中序序列的第一个元素索引；
第三个参数表示序列长度；
第四个参数表示前序序列；
第五个参数表示后序序列；
第六个参数用于保存结果；
先来考虑终止条件是什么，也就是什么时候结束递归，当我们的根结点为空的时候终止，对应这里就是序列长度为零的时候。
if (length == 0) { return;}
接着考虑处理逻辑，也就是找到索引 i：
int i = 0;while (insequence[inindex + i] != presequence[preindex]) { i++;}
然后开始向下递归：
preandintopost(preindex + 1, inindex, i, presequence, insequence, result);preandintopost(preindex + i + 1, inindex + i + 1, length - i - 1, presequence, insequence, result);result.add(presequence[preindex]);
因为推导的是后序序列，所以顺序如上，添加根结点的操作是在最后的。前三个参数如何得出来的呢，我们走一下第一次遍历就可以得出来。
前序序列的第一个结点 1 在中序序列中的索引为 2，此时
左子树的中序系列起始索引为总序列的第 1 个索引，长度为 2；
左子树的前序序列起始索引为总序列的第 2 个索引，长度为 2；
右子树的中序系列起始索引为总序列的第 3 个索引，长度为 length - 3；
右子树的前序序列起始索引为总序列的第 3 个索引，长度为 length - 3；
完整代码如下：
/** * 根据前序和中序推导后序 * * @param preindex 前序索引 * @param inindex 中序索引 * @param length 序列长度 * @param presequence 前序序列 * @param insequence 中序序列 * @param result 结果序列 */private void preandintopost(int preindex, int inindex, int length, int[] presequence, int[] insequence, list<integer> result) { if (length == 0) { return; } int i = 0; while (insequence[inindex + i] != presequence[preindex]) { i++; } preandintopost(preindex + 1, inindex, i, presequence, insequence, result); preandintopost(preindex + i + 1, inindex + i + 1, length - i - 1, presequence, insequence, result); result.add(presequence[preindex]);}
参考链接• 维基百科 - 二叉树（https://zh.wikipedia.org/wiki/%e4%ba%8c%e5%8f%89%e6%a0%91）
推荐教程：《java教程》
以上就是详解java中二叉树的深度优先遍历的详细内容。