代码随想录 — 栈与队列、二叉树

对应 leetcode-master：栈与队列理论基础、232/225/20/1047/150/239/347、二叉树理论、遍历、层序、翻转/对称/深度、构造、BST 等。

---

一、栈与队列理论基础

• 栈：先进后出（LIFO）；不提供遍历，只提供 push/pop/top 等接口。底层可以是数组或链表（如 deque），属于容器适配器。
• 队列：先进先出（FIFO）；同样不提供遍历。底层常用 deque。
• 理解：栈适合「最近相关」「对称匹配」「深度优先」；队列适合「一层一层」「广度优先」。很多语言里栈/队列是对某种底层容器的封装，知道「只能一端进出一端出」即可。

---

二、栈与队列经典题（思路要点）

题目	要点
232 用栈实现队列	两个栈：一个负责入队（push），一个负责出队（pop/peek）。出队时若「出队栈」为空，先把「入队栈」全部倒入再出。
225 用队列实现栈	用一个队列即可：每次 push 时把新元素入队，再把队内原有元素依次出队再入队，这样新元素就到了队头，等价于栈顶。
20 有效的括号	左括号入栈，右括号时看栈顶是否匹配；最后栈空则有效。注意只有右括号、栈空时来右括号等情况。
1047 删除相邻重复项	栈顶等于当前字符则弹栈并跳过，否则入栈；最后栈内字符逆序即结果（或再用一个栈/数组反转）。
150 逆波兰表达式	遇到数字入栈，遇到运算符则弹出两个数运算后结果入栈；注意减法和除法的顺序（先弹出的是右操作数）。
239 滑动窗口最大值	单调队列：维护一个从队头到队尾单调减的双端队列，存下标；窗口右移时去掉超出窗口的队头、新元素从队尾入队并踢掉比它小的，队头即当前窗口最大值。
347 前 K 个高频元素	先用 Map 统计频率，再用堆（或排序）：维护大小为 k 的小顶堆，堆顶是当前第 k 大频率，超过 k 就弹出堆顶；最后堆中即为前 k 个。

---

三、二叉树理论基础（有助于写题）

• 种类：满二叉树（每层都满）、完全二叉树（最后一层从左到右连续）、二叉搜索树 BST（左 < 根 < 右）、平衡二叉搜索树（左右高度差 ≤ 1，如 AVL）。map/set 的底层可以是平衡二叉搜索树，所以增删查 O(log n)。
• 存储：链式（left/right 指针）常用；顺序存储时父节点 i 的左子 2i+1、右子 2i+2。
• 遍历：
  • 深度优先：前序（中左右）、中序（左中右）、后序（左右中）— 「前中后」指根的处理顺序。
  • 广度优先：层序遍历，用队列，每次把当前层节点出队并把其子节点入队。

递归与栈：前中后序的递归实现，本质是系统栈；迭代实现用显式栈。层序用队列。

---

四、二叉树 — 递归遍历与层序

• 递归：终止条件一般是 root === null；先处理根（前序）或左或右，再递归左右。回溯是递归的副产品，在「修改状态 → 递归 → 恢复状态」时就是在回溯。
• 迭代（栈）：前序：先压根，每次弹出一个并访问，再先右后左入栈（这样先访问左）。中序：指针往左走到底并一路入栈，再弹栈访问，再往右。后序：可改为「中右左」再反转，或按「访问标记」区分已处理子树的节点。
• 层序：队列 + 每层记个数（或每层一个数组），先入根，每次取一层节点，把其非空子节点入队，直到队列空。

---

五、二叉树 — 属性与简单递归

题目	思路要点
226 翻转二叉树	交换左右子，再递归翻转左右子树；前序或后序均可。
101 对称二叉树	判断两棵树是否镜像：比较根值，再递归比较「左的左 vs 右的右」「左的右 vs 右的左」。
104 最大深度	根为 null 返回 0；否则 1 + max(左深度, 右深度)。
111 最小深度	注意：若某子为 null，不能算成 0 取 min，应只算另一侧；叶子才是「1」。
222 完全二叉树节点数	可递归左右子树节点数相加 +1；完全二叉树可结合满二叉树公式优化。
110 平衡二叉树	后序求高度，若左右高度差 >1 则返回 -1 表示不平衡，否则返回高度。
257 所有路径	DFS，维护路径数组，到叶子时把路径加入结果；回溯时 pop。
404 左叶子之和	判断「左叶子」：当前节点的左孩子存在且左孩子是叶子；递归累加。
112 路径总和	到叶子时判断剩余 sum 是否等于当前值；否则递归 left/right 并传 sum - root.val。

---

六、二叉树 — 构造与 BST

• 106 从中序与后序构造：后序最后一个为根，在中序里找到根，分出左子树区间和右子树区间，再递归构造左右子树（注意后序里左右子树的区间划分）。
• 105 从前序与中序构造：前序第一个为根，其余同 106。
• 654 最大二叉树：在区间内找最大值作为根，递归左右区间。
• 700 二叉搜索树中的搜索：根据 val 与根比较，小则搜左，大则搜右。
• 98 验证二叉搜索树：中序遍历应为严格递增；或递归时传「当前子树的值域上下界」。
• 530 最小绝对差：BST 中序得到有序序列，相邻差最小即答案。
• 501 众数：BST 中序，统计连续相同值的个数，更新众数。
• 236 最近公共祖先：后序：若当前根为 p 或 q 或 null 则返回；否则递归左右，若左右都非空则当前根为 LCA；若一侧非空则返回该侧结果。
• 235 BST 最近公共祖先：利用 BST 性质：若 p、q 都小于根则 LCA 在左；都大于根在右；否则根即为 LCA。
• 701/450 插入/删除：插入到叶子；删除分三种情况（无子、单子、双子—用右子树最小节点替代）。
• 108 有序数组转 BST：中点作根，递归左右半数组。
• 538 累加树：反中序（右中左）遍历，累加和赋给当前节点。

---

七、二叉树总结

类型	方法
遍历	前中后序（递归/迭代）、层序（队列）
属性	深度、对称、路径和、左叶子等 — 定义好递归含义，注意叶子与 null 的边界
构造	用根划分中序得到左右区间，再划分前序/后序的对应区间递归
BST	中序有序、搜索/插入/删除、LCA 利用大小关系

建议：层序遍历、226/101/104、106/105、98、236 要熟；写递归时先想「当前节点要返回什么、左右子返回什么」。

---

附：核心代码模板

二叉树节点定义

// JavaScript
class TreeNode {
  constructor(val = 0, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

前中后序递归遍历

// JavaScript
function preorder(root, res = []) {
  if (!root) return res;
  res.push(root.val);       // 前序：中 → 左 → 右
  preorder(root.left, res);
  preorder(root.right, res);
  return res;
}

function inorder(root, res = []) {
  if (!root) return res;
  inorder(root.left, res);
  res.push(root.val);       // 中序：左 → 中 → 右
  inorder(root.right, res);
  return res;
}

层序遍历（BFS）

// JavaScript — 时间 O(n)
function levelOrder(root) {
  if (!root) return [];
  const res = [], queue = [root];
  while (queue.length) {
    const level = [], 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;
}

将有序数组转为二叉搜索树

function sortedArrayToBST(nums) {
	function build(l, r) {
	  if (l > r) return null;
	  const mid = (l + r) >> 1;
	  const root = new TreeNode(nums[mid]);
	  root.left = build(l, mid - 1);
	  root.right = build(mid + 1, r);
	  return root;
	}
	return build(0, nums.length - 1);
}

计算高度 （深度）

  /**
   * 二叉树高度：从节点到最远叶子的最长路径边数
   * 空树高度 -1，单节点高度 0
   * 时间 O(n)
   */
  function treeHeight(root) {
    if (!root) return -1;
    return 1 + Math.max(treeHeight(root.left),
  treeHeight(root.right));
  }

  // 若定义「空树为 0，单节点为 1」：

  function treeHeight(root) {
    if (!root) return 0;
    return 1 + Math.max(treeHeight(root.left),
  treeHeight(root.right));
  }
  
   /**
   * 节点深度：从根到该节点的边数
   * 根深度 0
   */
  function nodeDepth(root, target) {
    function dfs(node, d) {
      if (!node) return -1;
      if (node === target) return d;
      const L = dfs(node.left, d + 1);
      if (L !== -1) return L;
      return dfs(node.right, d + 1);
    }
    return dfs(root, 0);
  }

  // 若用 val 比较：

  function nodeDepth(root, targetVal) {
    function dfs(node, d) {
      if (!node) return -1;
      if (node.val === targetVal) return d;
      const L = dfs(node.left, d + 1);
      if (L !== -1) return L;
      return dfs(node.right, d + 1);
    }
    return dfs(root, 0);
  }

最近公共祖先（LCA）

// JavaScript — 时间 O(n)
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;
}

用栈实现队列

// JavaScript
class MyQueue {
  constructor() {
    this.inStack = [];
    this.outStack = [];
  }
  push(x) { this.inStack.push(x); }
  pop() {
    if (!this.outStack.length) {
      while (this.inStack.length) this.outStack.push(this.inStack.pop());
    }
    return this.outStack.pop();
  }
  peek() {
    const val = this.pop();
    this.outStack.push(val);
    return val;
  }
  empty() { return !this.inStack.length && !this.outStack.length; }
}