前端算法与数据结构面试：底层逻辑解读与大厂真题训练

从面试的角度看，性价比最高的知识体系则无疑是算法与数据结构。

算法逃不掉

算法一次学习 终生受用

数组

改变原数组 pop 尾部删除 push 尾部添加 shift 头部删除 unshift 头部添加

splice 第一个参数 确定索引位置 第二个参数 确定删除个数 第三个参 数位置 添加到数组的元素

栈 后进先出 push pop

队列 先进先出 push shift

链表

function ListNode(val) {
  this.val = val
  this.next = null
}
const node1 = new ListNode(1)
node1.next = new ListNode(2)

链表的添加

const node3 = new ListNode(3)
node1.next.next = node3

链表的中间添加

const node = new NodeList(1)

const node2 = new NodeList(2)

const node3 = new NodeList(3)

node.next = node2
// node3 插入中间
node3.next = node.next
node.next = node3

链表的删除 找到目标的前驱结点

node.next = node.next.next

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

链表的插入/删除效率较高，而访问效率较低；数组的访问效率较高，而插入效率较低。

树

树根->根节点 树枝->边 树枝端点->结点 树叶->叶子结点

树的层

度就是结点有多少边

叶子结点到目标结点经过的边

js 数据结构定义

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

// 树结点添加
const node = new TreeNode(1)
node.left = new TreeNode(2)
node.right = new TreeNode(3)

！！树的遍历

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

左子树一定先于右子树遍历

根的先后遍历就是叫先中后序遍历

所谓的“先序”、“中序”和“后序”，“先”、“中”、“后”其实就是指根结点的遍历时机。

如何满足根结点遍历顺序 其实就是满足输出时按照 先 中 后 打印

// 递归的实现 数的遍历
function a(root) {
  if (!root) {
    return
  }
  console.log(a.val) // 先序
  a(root.left)
  console.log(a.val) // 中序
  a(root.right)
  console.log(a.val) // 后序
}
// 迭代法实现二叉树的先、中、后序遍历
const preorderTraversal = function (root) {
  const res = []
  if (!root) {
    return
  }
  const stack = []

  while (stack.length) {
    const cur = stack.pop()
  }
}

TIP

为什么要分 先 中 后

因为要根据顺序来拿到根节点 3 中状态不同的顺序

先序 根节点位于第一个位置 所以我可以输出来