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

前言

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

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

快速上手——从 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);
}

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

当前遍历的结点值是： 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