前端就该用JS写算法 -- 树 -- 简略的那 30%
这里优先选择了 LeetCode 热题 HOT 100 中的树题，毕竟刷题的边际收益就是冲击须要算法的面试，所以 Hot 优先级更高。
二叉树的遍历
递归遍历
- 递归的时候前中后序都能间接解决完了
- 递归是前中后序遍历最简略也是最容易出了解的办法，不懂的画个图就好了
迭代遍历 -- 双色标记法
- 应用色彩标记节点状态，新节点为红色，曾经拜访的节点为灰色 -- 能够用数字或者其余任意标签标示
- 如果遇到的节点是红色，则标记为灰色，而后将右节点，本身，左节点一次入栈 -- 中序遍历
- 如果遇到的节点是灰色的，则将节点输入
- 留神这里是用 stack 栈来存储的，所以是后进先出，所以如果是中序遍历，左 - 中 - 右 ，那么在插入栈的时候要反过来 右 - 中 - 左
依照那个男人的批示，失常咱们就用递归做就好，就如同咱们做非排序题排序的时候，sort 一下就好了，然而一旦面试官问到用另外的迭代形式的时候，咱们再套个模板，会比记住多个迭代写法要简略，毕竟内存容量无限，而后续遍历的迭代写法的确挺坑的，能省一点内存就省一点吧
144. 二叉树的前序遍历
// 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 二叉树的中序遍历
// 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. 二叉树的后序遍历
// 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}参考视频：传送门
101. 对称二叉树
剖析
- 对称二叉树，其实是要求是否镜像对齐，所以递归过程至多须要两个根节点，而后 dfs 次要就是判断是否是对称的两棵树
- 这里是自顶向下调配互相比拟的子树节点 left 和 right，而后再自底向上的返回最终后果
- 在某一次dfs中，如果比拟单方都是 null，那么证实比拟单方是对称的；如果呈现只有一方有值，或者单方有值然而值不一样的时候，返回false；
- 每次递归都是左右外层形成比拟，左右内层形成比拟
- 工夫复杂度: O(h), 其中 h 是树的高度
// 101. 对称二叉树var isSymmetric = function (root) { if (!root) return false; const dfs = (left, right) => { if (!left && !right) return true; if (!left || !right || left.val !== right.val) return false; return dfs(left.left, right.right) && dfs(left.right, right.left); }; return dfs(root.left, root.right);};104. 二叉树的最大深度
- 应用树的三种搜寻形式，层序，自顶向下的dfs，自底向上的递归dfs
层序遍历
- 无论是深度，层数等，间接用层序遍历找到最初一层的最初一个叶子节点即可
- 工夫复杂度 O(N), 空间复杂度 O(K) -- K 是最大宽度
// 104. 二叉树的最大深度/** * 1.无论是深度，层数等，间接用层序遍历找到最初一层的最初一个叶子节点即可 */ var maxDepth = function(root) { if(!root) return 0 let ret = 0 const queue = [] queue.push(root) while(queue.length){ ret++ // 进入一层 let len = queue.length while(len--){ // 层序遍历 const root = queue.shift() if(root.left) queue.push(root.left) if(root.right) queue.push(root.right) } } return ret}dfs -- 自顶向下
- 咱们在计算层数的时候，能够思考到，没遍历一层，就携带一个参数，这个参数是一个标记，比如这里就是深度 depth
- 这样当咱们遍历到叶子节点的时候，都能够和最大值比对一下，而后完结这一条路线
- 工夫复杂度 O(N), 空间复杂度 O(D) -- D 是深度
/** * 1. 自顶向上，带个层数参数，断定为叶子节点就进行最大值判断 */var maxDepth = function (root) { if(!root) return 0 let ret = 0; const dfs = (root, depth) => { if (root.left) dfs(root.left, depth + 1); if (root.right) dfs(root.right, depth + 1); // 走到这的时候，证实是叶子节点了，所以取最大值，就完结这一次的 ret = Math.max(ret, depth); }; dfs(root, 1); return ret;};递归 -- 自低向上
- 既然有自顶向下，那么当然就有自低向上了；
- 就我肤浅的算法能力而已，自顶向下就是带参数的深度优先遍历 DFS, 而自低向上，是递归，须要dfs 到了底部，而后归到根节点，所以这里用的是 recursion 作为办法名。
- 自顶向下是从根节点开始算一层深度，而后跑到叶子节点完结；自低向上反过来，跑到最底层，而后一直求叶子结点的最大深度，然加上本身返回到下层
- 工夫复杂度 O(N), 空间复杂度 O(1)
// 自低向上var maxDepth = function (root) { const recursion = (root) => { // 只是到了底部，所以高度为 0 if (!root) return 0; // 每一个节点的高度是多少，就是两个节点树的最大高度+本人所处的这一层1 return Math.max(recursion(root.left), recursion(root.right))+1; }; return recursion(root);};226. 翻转二叉树
自底向上
- 因为要求的是反转二叉树，对于任意一颗子树，其实都是要做一样的操作，所以能够先递到叶子节点，而后开始进行翻转
- 自底向上将翻转好的子树传递到下层的节点，直到最初的根节点，失去了两课翻转好的树，而后替换一下一下地位就好了
- 工夫复杂度 O(N)
// 226. 翻转二叉树var invertTree = function (root) { const dfs = (root) => { // 达到了最底部，间接返回 null if (!root) return null; // 1.递归获取翻转后的左右子树 const left = dfs(root.left) const right = dfs(root.right) // 2.反转两棵树的地位 root.left = right root.right = left // 最初返回这个反转之后的树 return root; }; return dfs(root);};