二叉树

什么是二叉树？

二叉树是由节点构成的层次结构，每个节点最多只能有 两个子节点：左孩子 (left) 和 右孩子 (right)

function TreeNode(val, left, right) {
  this.val = (val === undefined ? 0 : val);
  this.left = (left === undefined ? null : left);
  this.right = (right === undefined ? null : right);
}

二叉树遍历

主要分为两大类：深度优先搜索 (DFS) 和 广度优先搜索 (BFS)

深度优先搜索 (DFS)

DFS 的核心是“一扎到底”。根据访问根节点 (Root) 的顺序不同，分为三种。我们用一棵简单的树为例：1 是根，2 是左孩子，3 是右孩子

      A (根)
    /   \
   B     C
  / \
 D   E

1. 前序遍历 (Pre-order)：根 -> 左 -> 右

前序遍历就像是一个**“先盖章再干活”**的过程。每到一个节点，先把这个节点放进结果列表。

• 步骤拆解：访问 A，它是根节点，直接放入：[A]走向左子树，到达 B，它是子树根节点，放入：[A, B]继续向左，到达 D，放入：[A, B, D]D 没有子节点了，回溯到 B，走向 B 的右孩子 E，放入：[A, B, D, E]B 这边处理完了，回溯到 A，走向 A 的右孩子 C，放入：[A, B, D, E, C]
• 最终结果： [A, B, D, E, C]

const preorderTraversal = (root) => {
  if (!root) return [];
  const stack = [root];
  const res = [];

  while (stack.length > 0) {
    const node = stack.pop(); // 弹出栈顶
    res.push(node.val);
    
    // 注意：栈是后进先出，所以先推入右孩子，再推入左孩子
    // 这样下次弹出时就是左孩子先出
    if (node.right) stack.push(node.right);
    if (node.left) stack.push(node.left);
  }
  return res;
};

2. 中序遍历 (In-order)：左 -> 根 -> 右

中序遍历像是**“从左往右投射”**。它必须先确认左边彻底处理完了，才轮到自己。

• 步骤拆解：从 A 开始，但不能放 A，得先看左边。来到 B，也不能放 B，继续看左边。来到 D，D 左边没了，放入：[D]回溯到 B，D（左）处理完了，现在轮到中（根），放入：[D, B]走向 B 的右孩子 E，E 左边没了，放入：[D, B, E]B 这整块（A 的左子树）都处理完了，回溯到 A，放入：[D, B, E, A]最后走向 A 的右孩子 C，放入：[D, B, E, A, C]
• 最终结果： [D, B, E, A, C]

/**
 * 中序遍历迭代版：左 -> 中 -> 右
 */
const inorderTraversal = function(root) {
  const res = [];
  const stack = []; // 手动维护的栈
  let curr = root;  // 指针，指向当前处理的节点

  // 只要指针不为空，或者栈里还有存货，就继续
  while (curr !== null || stack.length > 0) {
    
    // 1. 一路向左，把路径上的节点全部压栈
    while (curr !== null) {
      stack.push(curr);
      curr = curr.left;
    }

    // 2. 左边到头了，弹出栈顶元素（即最左下的节点）
    curr = stack.pop();
    
    // 3. 处理节点（中）
    res.push(curr.val);

    // 4. 转向右子树
    // 如果右子树为空，下次循环会直接进入第2步，继续弹出父节点
    curr = curr.right;
  }

  return res;
};

3. 后序遍历 (Post-order)：左 -> 右 -> 根

后序遍历像是**“搞定小的再搞大的”**。只有当左右两个孩子都处理完了，父节点才会被放进去。

• 步骤拆解：从 A -> B -> D，D 的左右都没有，最先放 D：[D]回到 B，还得看右边，走向 E，E 也没有左右，放入：[E]：[D, E]现在 B 的左右都处理完了，放入 B：[D, E, B]回到 A，不能放 A，得看 A 的右边。走向 C，C 也没有左右，放入：[D, E, B, C]最后，A 的左右子树都处理完了，放入 A：[D, E, B, C, A]
• 最终结果： [D, E, B, C, A]

var postorderTraversal = function(root) {
    if (!root) return [];
    let res = [];
    let stack = [];
    let curr = root;
    let prev = null; // 核心：记录“刚走出来”的那个门

    while (curr !== null || stack.length > 0) {
        // 1. 尽可能往左走
        while (curr !== null) {
            stack.push(curr);
            curr = curr.left;
        }

        // 2. 看一眼栈顶
        curr = stack[stack.length - 1];

        // 3. 判断是否可以处理当前根节点
        // 条件：没有右孩子，或者右孩子刚刚被处理完(prev)
        if (curr.right === null || curr.right === prev) {
            res.push(curr.val); // 只有这时候才处理
            stack.pop();        // 处理完才真正弹出
            prev = curr;        // 更新标记
            curr = null;        // 确保下一轮去弹栈
        } else {
            // 4. 否则，去处理右边
            curr = curr.right;
        }
    }
    return res;
};

层序遍历

如果说 DFS 是“探险家”，不撞南墙不回头；那么层序遍历就是“剥洋葱”，必须一层一层、从左往右地扫射

      A
    /   \
   B     C
  / \     \
 D   E     F

结果：[A, B, C, D, E, F ]

关键工具：队列 (Queue)

在实现 DFS 时，我们利用的是“栈”（先进后出），所以能回溯。
但层序遍历要求先看到的节点先处理，这完全符合**“队列”（First In, First Out - FIFO）**的特性。

口诀： 根节点入队 -> 出队 -> 带出左右孩子入队 -> 循环。

var levelOrder = function(root) {
    if (!root) return [];
    
    const res = [];
    const queue = [root]; // 1. 初始化队列，放入根节点

    while (queue.length > 0) {
        const levelSize = queue.length; // 2. 核心：记录当前层的节点数量
        const currentLevel = []; // 存放当前层的结果

        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift(); // 3. 出队
            currentLevel.push(node.val);

            // 4. 将左右孩子推入队列，供下一层循环使用
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }

        res.push(currentLevel); // 5. 把这一层的结果存入总结果
    }

    return res;
};