全部标签
写点什么
OpenHarmony算法元宇宙MySQL移动开发学习方法Web3.0高效工作数据库Python音视频前端AI大数据团队管理程序员运维深度思考低代码redisgolang微服务架构flutter 查看更多

前端 leetcde 算法面试套路之二叉树

作者：js2030code
  • 2022-12-15
    浙江

  • 本文字数：3874 字

    阅读完需：约 13 分钟

前端就该用 JS 写算法 -- 树 -- 简单的那 30%

这里优先选择了 LeetCode 热题 HOT 100 中的树题，毕竟刷题的边际收益就是冲击需要算法的面试，所以 Hot 优先级更高。

二叉树的遍历

递归遍历


  1. 递归的时候前中后序都能直接处理完了

  2. 递归是前中后序遍历最简单也是最容易出理解的方法，不懂的画个图就好了


迭代遍历 -- 双色标记法


  1. 使用颜色标记节点状态，新节点为白色，已经访问的节点为灰色 -- 可以用数字或者其他任意标签标示

  2. 如果遇到的节点是白色，则标记为灰色，然后将右节点，自身，左节点一次入栈 -- 中序遍历

  3. 如果遇到的节点是灰色的，则将节点输出

  4. 注意这里是用 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. 对称二叉树

分析

  1. 对称二叉树，其实是要求是否镜像对齐，所以递归过程至少需要两个根节点，然后 dfs 主要就是判断是否是对称的两棵树

  2. 这里是自顶向下分配相互比较的子树节点 left 和 right，然后再自底向上的返回最终结果

  3. 在某一次 dfs 中，如果比较双方都是 null，那么证明比较双方是对称的；如果出现只有一方有值，或者双方有值但是值不一样的时候，返回 false；

  4. 每次递归都是左右外层构成比较，左右内层构成比较

  5. 时间复杂度: 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

层序遍历

  1. 无论是深度，层数等，直接用层序遍历找到最后一层的最后一个叶子节点即可

  2. 时间复杂度 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 -- 自顶向下

  1. 我们在计算层数的时候，可以考虑到，没遍历一层，就携带一个参数，这个参数是一个标记，比方这里就是深度 depth

  2. 这样当我们遍历到叶子节点的时候，都可以和最大值比对一下，然后结束这一条路线

  3. 时间复杂度 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);};
复制代码


划线
评论
复制
发布于: 刚刚阅读数: 3
用户头像

js2030code

关注

还未添加个人签名 2022-09-14 加入

还未添加个人简介

评论

发布
暂无评论
Copyright © 2022, Geekbang Technology Ltd. All rights reserved. 极客邦控股（北京）有限公司 | 京 ICP 备 16027448 号 - 5京公网安备京公网安备 11010502039052号
前端leetcde算法面试套路之二叉树_js2030code_InfoQ写作社区