壹 ? 引
按照一天一题的速度，不知不觉已经刷了快两多月的leetcode了，因为本人较为笨拙，一道简单的题有时候也会研究很久，看着提交了两百多次，其实也才解决了70来道简单题，对于二分法，双指针等也只是有个初步概念，并非熟练。
若你有注意我以往题解文章，会发现我做过的大多题型均以数组和字符串为主。这是因为我在选择题目的时候始终将自己限制在熟悉的知识体系里，我非常害怕树，害怕递归，害怕动态规划。我深知害怕解决不了问题，自己始终得面对它们，所以今天我决定开始啃树了（学习树形结构不是啃树皮），懦弱的心做出稍微勇敢的决定。不积跬步，无以至千里；不积小流，无以成江海，愿你我共勉，那么本文开始。
贰 ? 前序遍历、中序遍历、后序遍历
在学习树之前，我想大家或多或少会联想到深度优先与广度优先相关概念。我在学习树的卡片时，结果又注意到前序遍历，中序遍历，后序遍历以及层序遍历等概念，这一下我就懵了。所以在学树之前，我们先 了解这些常见的搜索规则。
贰 ? 壹 前序遍历
前序遍历可以说最符合大家阅读树结构的查询顺序，它满足根节点=>左子树=>右子树的顺序，我们来看个例子：
如上图，其中A为根节点，B为左子树，C为右子树，所以遍历顺序为ABC。
我们再看看层级复杂点的二叉树结构，如下：
还是一样的套用上面的规律，首先是根节点A，之后遍历左子树B，而B又有自己的左子树D和右子树E，所以BDE又可以看成一个独立二叉树，因此遍历完B之后，紧接着就是遍历左子树D与右子树E。
E又有自己的左子树和右子树，因此遍历完E紧接着就是GH，到这里左子树完整遍历结束。于是来到右子树C，由于C没有左子树，所以紧接着遍历F，F遍历完又遍历了自己的左子树I，到这里遍历结束。所以完整的顺序为ABDEGHCFI。
我们永远先遍历根节点，紧接着判断有没有左子树，如果有接着遍历，而左子树也可以有自己的左子树与右子树，所以我们可以用递归来做到遍历。
来看一道题，题目来源144. 二叉树的前序遍历，题目描述如下：
给定一个二叉树，返回它的 前序 遍历。
示例:
输入: [1,null,2,3]
1 2 / 3输出: [1,2,3]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
让我们尝试实现它：
/**
* @param {TreeNode} root
* @return {number[]}
*/
var preorderTraversal = function(root) {
let res = [];
// 遍历函数
function traversal(root) {
if (root !== null) {
// 访问根节点的值
res.push(root.val);
if (root.left) {
// 递归遍历左子树
traversal(root.left);
};
if (root.right) {
// 递归遍历右子树
traversal(root.right);
};
};
};
traversal(root);
return res;
};
贰 ? 贰 中序遍历
中序遍历满足左子树=>根节点=>右子树的顺序进行查询，我们还是以简单二叉树为例。
当跑到到根节点B时，先得看看有没有左子树，正好有，所以先遍历了左子树A之后才是B，最后遍历右子树C，所以完整顺序顺序为ABC。
我们再来用中序遍历分析稍微复杂的二叉树，如下图：
从F开始，先看有没有左子树，因为有于是成功跑到了B，注意此时并不是直接取到B，由于B也有左子树，所以第一个遍历到的节点其实是A，而A没有其它分支了，所以紧接着遍历A的根节点B，然后跑到B的右子树D。而D也有自己的左子树与右子树，所以D不能被立刻遍历，而是先遍历C，然后才是D，最后是E。到这里F节点的左子树全部遍历完成，此时顺序为ABCDEF。
我们再看F的右子树，由于G没有左子树，所以直接遍历G，然后跑到G的右子树I，但I有左子树，所以先取H，再取I。结合上面，此二叉树的中序遍历顺序为ABCDEFGHI，我是以字母顺序提前排好了遍历顺序，大家陌生就多自己走几遍。
那么如何实现一个中序遍历呢，很简单，将前序遍历代码换个顺序就好了，我们始终先遍历节点的左子树，子又有左子树那就一直往下找，找到底才是当前左子树根节点，最后右子树。
看一道题，题目来自leetcode94. 二叉树的中序遍历，描述如下：
给定一个二叉树，返回它的中序遍历。
示例:
输入: [1,null,2,3]
1 2 / 3输出: [1,2,3]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
/**
* @param {TreeNode} root
* @return {number[]}
*/
var inorderTraversal = function(root) {
let res = [];
// 遍历函数
function traversal(root) {
if (root !== null) {
if (root.left) {
// 递归遍历左子树
traversal(root.left);
};
// 访问根节点的值
res.push(root.val);
if (root.right) {
// 递归遍历右子树
traversal(root.right);
};
};
};
traversal(root);
return res;
};
贰 ? 叁 后序遍历
后序遍历满足左子树=>右子树=>根节点的顺序进行查询，还是从简单二叉树开始：
从根节点C出发，先访问左子树A，紧接着右子树B，最后根节点C，所以顺序为ABC。
我们再来看一个较为复杂的二叉树，如下：
还是从根节点I出发，于是成功找到了左子树E，而E也有自己的左子树，所以第一个遍历到了A，紧接着来到E的右子树D，但D也有自己的左右子树，所以第二个遍历的是B，紧接着是C，最后是根节点D，根节点E。到这里，左子树遍历完成，顺序为ABCDE。
我们再来看I的右子树H，由于H有右子树G，所以H不能被遍历，G也有自己的左子树F，于是遍历到了F，G没右子树，于是F之后就是G，谨记着H，到这里I的右子树遍历完成，最后遍历根节点I。所以完整的顺序为ABCDEFGHI，顺序还是与字母顺序一致，大家跟着思路多多感受。
看到题，题目来自leetcode145. 二叉树的后序遍历，题目描述如下：
给定一个二叉树，返回它的后序遍历。
示例:
输入: [1,null,2,3]
1 2 / 3输出: [1,2,3]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
那么如何实现它呢？还是将上面的实现换个顺序即可。
/**
* @param {TreeNode} root
* @return {number[]}
*/
var postorderTraversal = function(root) {
let res = [];
// 遍历函数
function traversal(root) {
if (root !== null) {
if (root.left) {
// 递归遍历左子树
traversal(root.left);
};
if (root.right) {
// 递归遍历右子树
traversal(root.right);
};
// 访问根节点的值
res.push(root.val);
};
};
traversal(root);
return res;
};
叁 ? 层序遍历
层序遍历满足从上到下，从左到右一层一层遍历的顺序，以简单的二叉树为例：
首先从根节点A开始，这是第一层，遍历完成往下一层推进，于是访问到了B和C，完整顺序为ABC。
我们再来看一个较为复杂的二叉树，由于层序遍历理解上还是较为容易，下图遍历顺序为ABCDEFGHI，确实是从上到下从左往右一层层往下推进的遍历顺序。
来看一道题，题目来自leetcode102. 二叉树的层序遍历，描述如下：
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
示例：
二叉树：[3,9,20,null,null,15,7],3 / 9 20 / 15 7返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]
让我们来实现它，我们每遍历一层，都会将本层节点装到一个数组里，每往下推进一层，我们都得创建一个新的子数组，实现如下：
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrder = function(root) {
let res = [];
function traversal(root, depth) {
if (root !== null) {
if (!res[depth]) {
res[depth] = [];
};
res[depth].push(root.val)
if (root.left) {
traversal(root.left, depth + 1);
};
if (root.right) {
traversal(root.right, depth + 1);
};
};
};
traversal(root, 0);
return res;
};
关于层序遍历我们来趁热打铁，再来补一道我昨天做的题，题目来自leetcode104. 二叉树的最大深度，描述如下：
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，3 / 9 20 / 15 7返回它的最大深度 3 。
注意，由于我们是要统计最大深度，所以第一层就应该是从1开始，这里直接贴代码：
/**
* @param {TreeNode} root
* @return {number}
*/
var maxDepth = function(root) {
let ans = 0;
if(root===null){
return ans;
};
function traversal(root,deepth){
// 始终取最大数为最深层级
ans = Math.max(ans,deepth)
if(root.left){
traversal(root.left,deepth+1);
};
if(root.right){
traversal(root.right,deepth+1);
};
};
// 从1开始
traversal(root,1);
return ans;
};
肆 ? 深度优先、广度优先与前序、中序、后序、层序遍历关系
那么我们经常听闻的深度优先DFS与广度优先（宽度优先）BFS又和前面的前序、中序、后序、层序遍历又有何关系呢？我想聪明的同学应该已经联想到了，前序、中序、与后序遍历均为深度优先。而层序遍历也就是所谓的广度优先了。
对比不难发现，深度优先更具钻研精神，只要子树还有子，就一直往下查找，至于顺序对应前中后的查找顺序。而广度是将每一层节点遍历完成为止，才会进入下一层。
伍 ? 总
需要说明的是，上述实现代码其实都不是最优做法，部分实现均借鉴了leetcode题解一套拳法??刷掉n个遍历树的问题一文。因为对于现在的我来说，最易理解的解答要优于更好的性能，至于性能提升还需要日后积累，那么到这里本文结束。