前端要用JS写算法——树——简单30%这里推荐LeetCode热门话题HOT100中的树题。毕竟刷题的边际收益是需要Algorithm面试的影响，所以Hot的优先级更高。二叉树遍历Recursivetraversal递归时，可以直接处理前中后序。递归是理解前中后序遍历最简单易行的方法。不懂就画图吧。迭代遍历——双色标记法用颜色标记节点状态，新节点为白色，访问过的节点为灰色——可以用数字或其他任意标签来标记。如果遇到的节点是白色的，则标记为灰色，然后将右节点、自身、左节点标记一次入栈——中序遍历，如果遇到的节点为灰色，则输出节点。注意这里是用栈来存储的，所以是后进先出的，所以如果是中序遍历，左-中-右，那么插入栈的时候，按照右-中-左倒序按照男人的指示。通常，我们只是使用递归来完成它。就像我们对非排序问题进行排序时，只需对其进行排序。但是一旦面试官问到我们使用另一种迭代写法时，我们可以重新设置一个模板，这样会比死记硬背多种迭代写法容易。毕竟内存容量有限，后续遍历的迭代写法确实比较取巧。如果可以节省一点内存，请节省一点。144.二叉树的前序遍历//144.二叉树的前序遍历/***@analysis--recursion*/varpreorderTraversal=function(root){constret=[];const递归=(root)=>{if(!root)return;ret.push(root.val);递归（root.left）；递归（root.right）；};递归（根）；returnret;};/***@analysis--迭代--双色标记法*1.用颜色标记节点状态，新节点为白色，访问过的节点为灰色--可标记带有数字或其他任意标签*2.如果遇到的节点是白色的，则标记为灰色，然后将右节点、自身、左节点一次入栈——中序遍历*3.如果节点遇到是灰色的，输出node*4.注意这里是用栈来存储的，所以是后进先出，这里是前序遍历，middle-left-right，那么插入栈的时候，应该是反转右-左-中*/varpreorderTraversal=function(root){constret=[];常量堆栈=[];stack.push([root,0]);//0是白色未处理，1是灰色处理while(stack.length){const[root,color]=stack.pop();if(root){if(color===0){//遇到白球时，插入--preorderstack.push([root.right,0]);stack.push([root.left,0]);堆。推（[根，1]）；}else{//遇到灰色球时，关闭网络ret.push(root.val);}}}returnret;};1.94二叉树的中序遍历//94.二叉树的中序遍历/***@analysis*1.递归时，可以直接处理前中后序*2、递归是理解前中后序遍历最简单易行的方法。不懂就画图画图就好了*/varinorderTraversal=function(root){constret=[]constrecursion=root=>{if(!root)returnrecursion(root.left)//这里是中序的，所以在两个递归之间，如果前序在前，后序在后ret.push(root.val)recursion(root.right)}recursion(root)returnret};/***@analysis--迭代--双色标记法*1.用颜色标记节点状态，新节点为白色，访问过的节点为灰色--可以用数字或其他任意标签标记*2.如果遇到的节点是白色的，就标记为灰色，然后把右边的节点，自己，左边的节点一次性入栈——中序遍历*3.如果遇到的节点是灰色的，输出node*4.注意这里是用栈来存储的，所以是后进先出的，所以如果是中序遍历，左中右，那么在插入栈的时候，一定要inturnright-middle-left*/varinorderTraversal=function(root){constret=[]conststack=[]stack.push([root,0])//0是白色未处理，1是灰色处理Overwhile(stack.length){const[root,color]=stack.pop()if(root){if(color===0){//如果遇到白球，则按顺序插入栈的遍历。push([root.right,0])stack.push([root,1])stack.push([root.left,0])}else{//如果遇到灰球，就收网ret.push(root.val)}}}返回ret};参考视频：传送门145.二叉树的后序遍历//145.二叉树的后序遍历/***@analysis--recursion*/varpostorderTraversal=function(root){constret=[]constdfs=(root)=>{if(!root)returndfs(root.left)dfs(root.right)ret.push(root.val)}dfs(root)returnret};/***@analysis--iteration--two-colorball*/varpostorderTraversal=function(root){constret=[]conststack=[]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])堆栈。push([root.left,0])}else{ret.push(root.val)}}}returnret}101.对称二叉树的对称二叉树分析其实是需要镜像对齐的，所以递归过程需要至少有两个根节点，然后dfs主要是判断是否是对称二叉树。这里将left和right的子树节点从上到下赋值，相互比较，然后在某个dfs中从下到上返回最终结果。如果比较的两边都是null，则证明比较的两边是对称的；如果只有一侧有值，或者两边都有值但值不同，则返回false；每次递归都是比较左右外层，左右内层比较耗时度：O(h)，其中h是树的高度//101.对称二叉树varisSymmetric=函数（root）{如果（！root）返回false；constdfs=(left,right)=>{if(!left&&!right)returntrue;如果(!left||!right||left.val!==right.val)返回false；返回dfs(左.左,右.右)&&dfs(左.右,右.左);};返回dfs(root.left,root.right);};104.二叉树的最大深度使用树的三种搜索方式，sequence，top-downdfs，bottom-uprecursivedfslayerOrdertraversal不管深度，层数等，直接使用layerordertraversal寻找最后一层的最后一个叶节点。时间复杂度O(N),空间复杂度O(K)--K是最大宽度//104.二叉树的最大深度/***1.不管深度，层数等，直接用序列遍历求最后一层的最后一个叶节点。Can*/varmaxDepth=function(root){if(!root)return0letret=0constqueue=[]queue.push(root)while(queue.length){ret++//进入一层letlen=queue.lengthwhile(len--){//层序遍历constroot=queue.shift()if(root.left)queue.push(root.left)if(root.right)queue.push(root.right)}}returnret}dfs--我们在计算从上到下的层数时，可以认为不遍历一层，就带了一个参数。这个参数是一个标志。例如，这里是深度。当我们遍历到叶子节点的时候，可以和最大值进行比较，然后结束这条路由。时间复杂度为O(N)，空间复杂度为O(D)--D为深度/***1.Top-up，带层数参数，判断为叶子时判断最大值节点*/varmaxDepth=function(root){if(!root)return0letret=0;constdfs=(root,depth)=>{if(root.left)dfs(root.left,depth+1);如果(root.right)dfs(root.right,depth+1);//此时证明是叶子节点，所以取最大值，结束这个即可ret=Math.max(ret,depth);};dfs（根，1）；返回ret;};当然，也有自下而上的；就我浅薄的算法能力而言，top-down是带参数的深度优先遍历DFS，bottom-up是递归，需要dfs到达底部再回到根节点，所以这里使用Recursion作为方法名称。从上到下，一层的深度从根节点开始计算，然后运行到叶子节点的末端；从下往上，一直跑到最底层，然后不断的寻找叶子节点的最大深度，然后把自己加回到上层时间复杂度O(N)，空间复杂度O(1)//从低到高varmaxDepth=function(root){constrecursion=(root)=>{//刚刚到达底部，所以高度为0if(!root)return0;//每个节点的高度是两个节点树的最大高度+你所在的层1returnMath.max(recursion(root.left),recursion(root.right))+1;};返回递归（根）；}；226。从下往上翻转二叉树，因为需求是将二叉树反转。对于任何一棵子树，其实都需要同样的操作，所以可以先传递给叶子节点，然后从下往上开始翻转，将翻转后的子树传递给上层节点，直到最后的根节点，得到翻转后的树为两节课，然后只是交换位置时间复杂度O(N)//226.翻转二叉树varinvertTree=function(root){constdfs=(root)=>{//到达底部，直接返回nullif(!root)返回空值；//1.递归获取翻转后的左右子树constleft=dfs(root.left)constright=dfs(root.right)//2.反转两棵树的位置root.left=rightroot.right=left//最后返回反向树returnroot;};返回dfs（根）；}；
