数组类技巧

  1. 滑动窗口；
  2. 双指针;
  3. 巧用排序；
  4. 巧用数据结构（Hash Map/Set，Stack，Priority Queue）
  5. 动态规划；
  6. 回溯；

字符串类技巧

和数组类似，唯一不同的一点是巧用各类字符串API和正则表达式；

二叉树框架

递归更为简单，但吃内存；

function func(root) {
    // 先序
    func(root.left);
    // 中序
    func(root.right);
    // 后序
}

迭代较为复杂，但一般效率较高；

先序

function preorder(root) {
  if (!root) return [];
  const res = [];
  const stack = [root];
  while (stack.length) {
    const node = stack.pop();
    res.push(node.val);
    // 栈是后进先出，先压右再压左，出栈顺序才是根、左、右
    if (node.right) stack.push(node.right);
    if (node.left) stack.push(node.left);
  }
  return res;
}

中序

function inorder(root) {
  const res = [];
  const stack = [];
  let node = root;
  while (node || stack.length) {
    // 一路向左，把路径上的节点压栈
    while (node) {
      stack.push(node);
      node = node.left;
    }
    node = stack.pop();
    res.push(node.val);
    node = node.right;
  }
  return res;
}

后序

function postorder(root) {
  if (!root) return [];
  const res = [];
  const stack = [root];
  // 按根、右、左遍历，最后整体反转，得到左、右、根
  while (stack.length) {
    const node = stack.pop();
    res.push(node.val);
    if (node.left) stack.push(node.left);
    if (node.right) stack.push(node.right);
  }
  return res.reverse();
}

层序

function levelOrder(root) {
  if (!root) return [];
  const res = [];
  const queue = [root];
  while (queue.length) {
    const level = [];
    // 先固定当前层的节点数，循环中入队的属于下一层
    const size = queue.length;
    for (let i = 0; i < size; i++) {
      const node = queue.shift();
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    res.push(level);
  }
  return res;
}

树框架

二叉树的题，90% 都能套进同一个递归骨架：

function traverse(root) {
  if (!root) return;
  // 先序：进入节点时做点什么
  traverse(root.left);
  // 中序：左子树处理完做点什么
  traverse(root.right);
  // 后序：离开节点时做点什么
}

写题时只需要回答三个问题：

  1. 进入节点时要做什么：记录路径、累加和、传下界/上界；
  2. 子节点要返回什么：深度、是否平衡、子树的和、找到的节点；
  3. 离开节点时要做什么：合并左右子树的结果、更新全局答案。

几个典型映射：

  • 求最大深度 / 直径：后序，1 + max(left, right)，直径在“离开节点”时用 left + right 更新全局最大值；
  • 路径总和：先序，把剩余目标值传给子节点，到叶子时判断是否为 0；
  • 验证 BST：先序传 (min, max) 上下界，或中序遍历判断是否严格递增；
  • 最近公共祖先：后序，左右子树各找到一个就返回当前节点；
  • 层序遍历：BFS + 队列，用 size 固定当前层节点数。
// 最大深度：后序的典型
function maxDepth(root) {
  if (!root) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

// 最近公共祖先：后序，左右都找到就返回自己
function lowestCommonAncestor(root, p, q) {
  if (!root || root === p || root === q) return root;
  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);
  if (left && right) return root;
  return left || right;
}

两个实践建议：

  • 递归先想清楚返回值语义，再写 base case，不要在人脑里模拟整个递归栈；
  • 树退化成链表时递归深度是 O(n)，节点数到 10^5 量级要改成显式栈或 Morris 遍历，否则会爆栈；
  • 层序遍历用 shift() 出队是 O(n)，数据量大时用索引指针或双端队列，别在循环里反复移动数组。
End of entry