前端算法与数据结构面试笔记

前言

学习观念:前端工程师如果不是为了面试,那么不建议花大力气折腾算法(尤其是在业余时间本身非常有限的情况下),你应该考虑把更多的时间用来做工程

所谓工程能力,本质是“解决问题的能力”,无论是硬编码实力、还是架构思想,其本质都是为了解决问题这个终极目标而服务

快速上手——从 0 到 1 掌握面试需要的数据结构(一)

数据结构层面需掌握

  • 数组
  • 队列
  • 链表
  • 树(主要讲二叉树)

快速上手——从 0 到 1 掌握面试需要的数据结构(二 )

在涉及链表删除操作的题目中,重点不是定位目标结点,而是定位目标结点的前驱结点

JS 数组未必是真正的数组

何谓“真正的数组”?在各大教材(包括百科词条)对数组的定义中,都有一个“存储在连续的内存空间里”这样的必要条件。

链表的插入/删除效率较高,而访问效率较低;数组的访问效率较高,而插入效率较低

快速上手——从 0 到 1 掌握算法面试需要的数据结构(三)

理解二叉树结构

二叉树是指满足以下要求的树:

  • 它可以没有根结点,作为一棵空树存在
  • 如果它不是空树,那么必须由根结点、左子树和右子树组成,且左右子树都是二叉树。如下图:

二叉树构造函数

// 二叉树结点的构造函数
function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

递归初相见——二叉树递归遍历的三种姿势

遍历方式有以下四种:

  • 先序遍历
  • 中序遍历
  • 后序遍历
  • 层次遍历

那么遍历的可能顺序也不过三种:

  • 根结点 -> 左子树 -> 右子树 先序遍历
  • 左子树 -> 根结点 -> 右子树 中序遍历
  • 左子树 -> 右子树 -> 根结点 后序遍历

先序遍历的编码实现:

// 所有遍历函数的入参都是树的根节点对象
function preorder(root) {
    // 递归边界,root 为空
    if (!root) {
        return;
    }
    // 输出当前遍历的节点值
    console.log('当前遍历的结点值是:', root.val);
    // 递归遍历左子树
    preorder(root.left);
    // 递归遍历右子树
    preorder(root.right);
}

各位现在完全可以再回过头来看一下我们前面示例的这棵二叉树:

img

当前遍历的结点值是: A
当前遍历的结点值是: B
当前遍历的结点值是: D
当前遍历的结点值是: E
当前遍历的结点值是: C
当前遍历的结点值是: F

中序遍历:

左子树 -> 根结点 -> 右子树:

// 所有遍历函数的入参都是树的根结点对象
function inorder(root) {
    // 递归边界,root 为空
    if (!root) {
        return;
    }

    // 递归遍历左子树
    inorder(root.left);
    // 输出当前遍历的结点值
    console.log('当前遍历的结点值是:', root.val);
    // 递归遍历右子树
    inorder(root.right);
}
当前遍历的结点值是: D
当前遍历的结点值是: B
当前遍历的结点值是: E
当前遍历的结点值是: A
当前遍历的结点值是: C
当前遍历的结点值是: F

后序遍历

左子树 -> 右子树 -> 根结点

function postorder(root) {
    // 递归边界, root 为空
    if (!root) {
        return;
    }
    // 递归遍历左子树
    postorder(root.left);
    // 递归遍历右子树
    postorder(root.right);
    // 输出当前遍历的结点值
    console.log('当前遍历的结点值是:', root.val);
}

输出结果:

当前遍历的结点值是: D
当前遍历的结点值是: E
当前遍历的结点值是: B
当前遍历的结点值是: F
当前遍历的结点值是: C
当前遍历的结点值是: A
Last Updated:
Contributors: johan