正文
在前端中确实用到不少与树相关的的知识，比方说 DOM 树，Diff 算法，包括原型链其实都算是树，学会树，其实对于学这些知识还是有比较大的帮助的，当然我们学算法还是得考虑面试，而树恰好也是一个大重点 -- 起码在前端而言；
主要原因在于，树它华而不实，比较下里巴人，需要抽象但是又能把图画出来不至于让你毫无头绪，简单而言就是看上去很厉害，但实际上也很接地气，俗称比较一般；要知道做前端的面试算法，考的不就是你有么得主动学习能力，抽象能力等，但是考虑到参差不齐的前端娱乐圈，考得难吧可能就全是漏网之鱼了，所以既要筛选出鱼，但是又不能难度过大，树就是那个比较适中的，所以赶紧刷起来吧朋友们；
这里本来是要遵照 3:5:2 难度来刷，预计刷个30题就差不多，但是实际中等题刷得欲罢不能，难题是欲仙欲死，容易题是味如嚼蜡，所以 XDM 担待一下。选题主要是那个男人精选的例题以及 Leetcode 中 HOT 题和字节专题，总的来说代表性还是够的，刷完应该大概或许能够应付一下树这方面的算法了。
如果觉得有那么点帮助，请点个赞留个言，点赞超过10个就更新下一part；好吧，即便不过也会更新，就是这么臭不要脸，大家伙加油吧，欧力给！！
二叉树的遍历
递归遍历
- 递归的时候前中后序都能直接处理完了
- 递归是前中后序遍历最简单也是最容易出理解的方法，不懂的画个图就好了
迭代遍历 -- 双色标记法
- 使用颜色标记节点状态，新节点为白色，已经访问的节点为灰色 -- 可以用数字或者其他任意标签标示
- 如果遇到的节点是白色，则标记为灰色，然后将右节点，自身，左节点一次入栈 -- 中序遍历
- 如果遇到的节点是灰色的，则将节点输出
- 注意这里是用 stack 栈来存储的，所以是后进先出，所以如果是中序遍历，左 - 中 - 右 ，那么在插入栈的时候要反过来 右 - 中 - 左
按照那个男人的指示，正常我们就用递归做就好，就好像我们做非排序题排序的时候，sort 一下就好了，但是一旦面试官问到用另外的迭代方式的时候，我们再套个模板，会比记住多个迭代写法要简单，毕竟内存容量有限，而后续遍历的迭代写法确实挺坑的，能省一点内存就省一点吧
144. 二叉树的前序遍历
代码语言：javascript复制// 144. 二叉树的前序遍历
/** * @分析 -- 递归 */
var preorderTraversal = function (root) {
const ret = [];
const recursion = (root) => {
if (!root) return;
ret.push(root.val);
recursion(root.left);
recursion(root.right);
};
recursion(root);
return ret;
};
/** * @分析 -- 迭代 -- 双色标记法 * 1. 使用颜色标记节点状态，新节点为白色，已经访问的节点为灰色 -- 可以用数字或者其他任意标签标示 * 2. 如果遇到的节点是白色，则标记为灰色，然后将右节点，自身，左节点一次入栈 -- 中序遍历 * 3. 如果遇到的节点是灰色的，则将节点输出 * 4. 注意这里是用 stack 栈来存储的，所以是后进先出，这里是前序遍历，中 - 左 - 右 ，那么在插入栈的时候要反过来 右 - 左 - 中 */
var preorderTraversal = function (root) {
const ret = [];
const stack = [];
stack.push([root, 0]); // 0 是白色未处理的，1 是灰色处理过的
while (stack.length) {
const [root, color] = stack.pop();
if (root) {
if (color === 0) {
// 遇到白球，则插入 -- 前序
stack.push([root.right, 0]);
stack.push([root.left, 0]);
stack.push([root, 1]);
} else {
// 遇到灰球，则收网
ret.push(root.val);
}
}
}
return ret;
};1.94 二叉树的中序遍历
代码语言：javascript复制// 94. 二叉树的中序遍历
/** * @分析 * 1. 递归的时候前中后序都能直接处理完了 * 2. 递归是前中后序遍历最简单也是最容易出理解的方法，不懂的画个图就好了 */
var inorderTraversal = function(root) {
const ret = []
const recursion = root => {
if(!root) return
recursion(root.left)
// 这里是中序，所以在两个递归之间，如果是前序就在前面，后序就在后面
ret.push(root.val)
recursion(root.right)
}
recursion(root)
return ret
};
/** * @分析 -- 迭代 -- 双色标记法 * 1. 使用颜色标记节点状态，新节点为白色，已经访问的节点为灰色 -- 可以用数字或者其他任意标签标示 * 2. 如果遇到的节点是白色，则标记为灰色，然后将右节点，自身，左节点一次入栈 -- 中序遍历 * 3. 如果遇到的节点是灰色的，则将节点输出 * 4. 注意这里是用 stack 栈来存储的，所以是后进先出，所以如果是中序遍历，左 - 中 - 右 ，那么在插入栈的时候要反过来 右 - 中 - 左 */
var inorderTraversal = function(root) {
const ret = []
const stack = []
stack.push([root,0]) // 0 是白色未处理的，1 是灰色处理过的
while(stack.length) {
const [root,color] = stack.pop()
if(root){
if(color === 0){
// 遇到白球，则插入 -- 中序遍历
stack.push([root.right,0])
stack.push([root,1])
stack.push([root.left,0])
}else{
// 遇到灰球，则收网
ret.push(root.val)
}
}
}
return ret
};145. 二叉树的后序遍历
代码语言：javascript复制// 145. 二叉树的后序遍历
/** * @分析 -- 递归 */
var postorderTraversal = function(root) {
const ret = []
const dfs = (root) => {
if(!root) return
dfs(root.left)
dfs(root.right)
ret.push(root.val)
}
dfs(root)
return ret
};
/** * @分析 -- 迭代 -- 双色球 */
var postorderTraversal = function(root) {
const ret = []
const stack = []
stack.push([root,0])
while(stack.length){
const [root,color] = stack.pop()
if(root) {
if(color === 0){
stack.push([root,1])
stack.push([root.right,0])
stack.push([root.left,0])
}else{
ret.push(root.val)
}
}
}
return ret
}刷题过程一些疑惑点
自顶向下(前序遍历)和自低向上(后续遍历)
这两个名词在很多讲树的题解中经常会出现，而这与我们遍历树求值到底关联点在哪里，慢慢刷题之后我发现，虽然 dfs 有三种形式，但在抽象到具体题目的时候，其实是属于不同的方法的。
对于前序遍历而言，就是先获取到根节点的信息，然后做了一定编码后，再向下遍历，这种遍历方式就是所谓的 自顶向下 的思维，我们从根节点开始，可以携带一定的信息，再继续往下遍历时，先处理，得到临时性结果，给顶层的节点作为信息；
对于自顶向下的遍历而已，遍历到根节点，就处理结束所有的节点，也相应的得到预期结果了，所以一般使用前序遍历方法解题的，都会声明一个全局变量，然后遍历完之后，返回这个值.
例子:563. 二叉树的坡度
代码语言：javascript复制分析
1. 自底向上返回子树值之和，然后求出对应的坡度，累加起来即可.
2. 需要注意的是，左右子树的累加值大小不确定，需要用绝对值
3. 时间复杂度 ${O(N)}$
var findTilt = function (root) {
let ret = 0;
const recursion = (root) => {
if (!root) return 0;
const left = recursion(root.left);
const right = recursion(root.right);
ret = Math.abs(left - right);
return left right root.val;
};
recursion(root);
return ret;
};对于后序遍历 而言，是想遍历到叶子节点，然后再向上去处理根节点，也就是所谓的 自底向上 ；
实际上，自底向上是一种递归的方法，先递 到叶子节点，处理完返回一定的值，再归回来，后续的处理都是根据子树的值作为入参的，所以不要被 遍历 迷惑，后续遍历 可不是遍历完就结束了，那才刚刚开始呢。
所以后面为了区分，在处理自底向上题目的时候，函数名字都不再使用 dfs，而是直接使用 recursion ；
例子:
判断遍历到边界，什么在叶子节点处判断，什么时候直接跑到 null 返回？
先来解释一下，在做 dfs 遍历的时候，我们需要遍历到叶子节点，然后做最终的处理，有的题目我们看到的是判 null 时返回 null/0 等；有的时候我们直接判断是否叶子节点，if(!root.left && !root.right)；
这是在刷题过程中感觉忒迷惑的地方，在最开始的时候，我喜欢使用 null ，因为它写的更少，而且顺便把根节点为空的边界也做了，最近刷的时候我开始觉得判断节点会更稳妥一点，而且不用做更深的处理，直到我再写
