乐趣区

关于leetcode:前端leetcde算法面试套路之二叉树

前端就该用 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);
};
退出移动版