leetcode 最常见的前端基础算法面试题汇总_leetcode前端算法题

把这些基础算法题掌握好，基础不牢地动山摇，后面中级题很多都是在这些基础题的基础上的。

二叉树

二叉树前中后遍历套路详解

前序遍历题目如下：
root节点是A节点（下图的A节点），然后让你按照下图数字的顺序依次打印出节点。

我们可以看到这其中的规律，就是深度优先遍历，先遍历左子树，再遍历右子树，这里我们不用递归，因为一些大厂严格要求二叉树遍历不用递归，递归太简单了。

重点思路就是：深度优先遍历，先遍历左子树，再遍历右子树，

所以，我们需要一套如何遍历一颗二叉树，并且是先左子树，再右子树的通用模板，如下

var Traversal = function(root) {
    const stack = [];
    while (root || stack.length){
      while(root){
        stack.push(root);
        root = root.left;
      }
      root = stack.pop();
      root = root.right;
    }
    return res;
};
1
2
3
4
5
6
7
8
9
10
11
12

我们结合图片发现这个遍历产生的整体压栈的顺序是

• A、B、D入栈，
• D出栈
• B出栈
• E入栈
• E出栈
• A出栈
• C入栈
• C出栈
• F入栈
• F出栈

我们把上面入栈的元素按顺序排列一下就是，A、B、D、E、C、F，而这就是前序遍历的顺序！解答完毕！

是不是很有意思，下面的中序遍历，我们看看出栈顺序是不是中序遍历的要求：D、B、E、A、C、F（这就是中序遍历的要求，好了，两个题解决）

放具体前序遍历代码：

var preorderTraversal = function(root) {
    // 初始化数据
    const res =[];
    const stack = [];
    while (root || stack.length){
      while(root){
        res.push(root.val);
        stack.push(root);
        root = root.left;
      }
      root = stack.pop();
      root = root.right;
    }
    return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

中序遍历是一个意思，在前序遍历的基础上改造一下

var preorderTraversal = function(root) {
    // 初始化数据
    const res =[];
    const stack = [];
    while (root || stack.length){
      while(root){
        stack.push(root);
        root = root.left;
      }
      root = stack.pop();
      res.push(root.val);
      root = root.right;
    }
    return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

后序遍历有点不太一样，但是套路是一样的，我们需要先遍历右子树，再遍历左子树，反着来，就可以了，代码如下：

var postorderTraversal = function(root) {
  // 初始化数据
    const res =[];
    const stack = [];
    while (root || stack.length){
      while(root){
        stack.push(root);
        res.unshift(root.val);
        root = root.right;
      }
      root = stack.pop();
      root = root.left;
    }
    return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

对称二叉树

这个题简而言之就是判断一个二叉树是对称的，比如说：
二叉树 [1,2,2,3,4,4,3] 是对称的。

   1
   / \
  2   2
 / \ / \
3  4 4  3
1
2
3
4
5

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

1
   / \
  2   2
   \   \
   3    3
1
2
3
4
5

思路：
递归解决：

• 判断两个指针当前节点值是否相等
• 判断 A 的右子树与 B 的左子树是否对称
• 判断 A 的左子树与 B 的右子树是否对称

function isSame(leftNode, rightNode){
    if(leftNode === null && rightNode === null) return true;
    if(leftNode === null || rightNode === null) return false;
    return leftNode.val === rightNode.val && isSame(leftNode.left, rightNode.right) && isSame(leftNode.right, rightNode.left)
}
var isSymmetric = function(root) {
    if(!root) return root;
    return isSame(root.left, root.right);
};
1
2
3
4
5
6
7
8
9

二叉树的最大深度

这个题在面试滴滴的时候遇到过，主要是掌握二叉树遍历的套路

• 只要遍历到这个节点既没有左子树，又没有右子树的时候
• 说明就到底部了，这个时候如果之前记录了深度，就可以比较是否比之前记录的深度大，大就更新深度
• 然后以此类推，一直比较到深度最大的

var maxDepth = function(root) {
    if(!root) return root;
    let ret = 1;
    function
1
2
3