跳到主要内容

遍历二叉树

问题​

手写实现二叉树的前序、中序、后序遍历（递归和迭代），以及层序遍历。

答案​

二叉树遍历是面试高频考点，需要掌握 DFS（深度优先）的三种遍历方式和 BFS（广度优先）的层序遍历。

二叉树节点定义​

class TreeNode<T = number> {
  val: T;
  left: TreeNode<T> | null;
  right: TreeNode<T> | null;

  constructor(val: T, left?: TreeNode<T> | null, right?: TreeNode<T> | null) {
    this.val = val;
    this.left = left ?? null;
    this.right = right ?? null;
  }
}

// 构建示例树
//       1
//      / \
//     2   3
//    / \   \
//   4   5   6
const tree = new TreeNode(
  1,
  new TreeNode(2, new TreeNode(4), new TreeNode(5)),
  new TreeNode(3, null, new TreeNode(6))
);

前序遍历（根 → 左 → 右）​

访问顺序：1 → 2 → 4 → 5 → 3 → 6

递归实现​

function preorderRecursive<T>(root: TreeNode<T> | null): T[] {
  const result: T[] = [];

  function traverse(node: TreeNode<T> | null) {
    if (!node) return;

    result.push(node.val);    // 根
    traverse(node.left);       // 左
    traverse(node.right);      // 右
  }

  traverse(root);
  return result;
}

迭代实现（栈）​

function preorderIterative<T>(root: TreeNode<T> | null): T[] {
  if (!root) return [];

  const result: T[] = [];
  const stack: TreeNode<T>[] = [root];

  while (stack.length) {
    const node = stack.pop()!;
    result.push(node.val);

    // 先右后左入栈，保证左子树先处理
    if (node.right) stack.push(node.right);
    if (node.left) stack.push(node.left);
  }

  return result;
}

中序遍历（左 → 根 → 右）​

访问顺序：4 → 2 → 5 → 1 → 3 → 6

递归实现​

function inorderRecursive<T>(root: TreeNode<T> | null): T[] {
  const result: T[] = [];

  function traverse(node: TreeNode<T> | null) {
    if (!node) return;

    traverse(node.left);       // 左
    result.push(node.val);    // 根
    traverse(node.right);      // 右
  }

  traverse(root);
  return result;
}

迭代实现（栈）​

function inorderIterative<T>(root: TreeNode<T> | null): T[] {
  const result: T[] = [];
  const stack: TreeNode<T>[] = [];
  let current = root;

  while (current || stack.length) {
    // 一直向左走到底
    while (current) {
      stack.push(current);
      current = current.left;
    }

    // 弹出并访问
    current = stack.pop()!;
    result.push(current.val);

    // 转向右子树
    current = current.right;
  }

  return result;
}

后序遍历（左 → 右 → 根）​

访问顺序：4 → 5 → 2 → 6 → 3 → 1

递归实现​

function postorderRecursive<T>(root: TreeNode<T> | null): T[] {
  const result: T[] = [];

  function traverse(node: TreeNode<T> | null) {
    if (!node) return;

    traverse(node.left);       // 左
    traverse(node.right);      // 右
    result.push(node.val);    // 根
  }

  traverse(root);
  return result;
}

迭代实现（双栈法）​

function postorderIterative<T>(root: TreeNode<T> | null): T[] {
  if (!root) return [];

  const result: T[] = [];
  const stack: TreeNode<T>[] = [root];

  while (stack.length) {
    const node = stack.pop()!;
    // 头插法，相当于逆序
    result.unshift(node.val);

    // 先左后右入栈
    if (node.left) stack.push(node.left);
    if (node.right) stack.push(node.right);
  }

  return result;
}

// 优化版：避免 unshift
function postorderIterativeOptimized<T>(root: TreeNode<T> | null): T[] {
  if (!root) return [];

  const result: T[] = [];
  const stack: TreeNode<T>[] = [root];

  while (stack.length) {
    const node = stack.pop()!;
    result.push(node.val);

    if (node.left) stack.push(node.left);
    if (node.right) stack.push(node.right);
  }

  return result.reverse();
}

迭代实现（单栈 + 标记法）​

function postorderWithFlag<T>(root: TreeNode<T> | null): T[] {
  if (!root) return [];

  const result: T[] = [];
  const stack: Array<{ node: TreeNode<T>; visited: boolean }> = [
    { node: root, visited: false },
  ];

  while (stack.length) {
    const { node, visited } = stack.pop()!;

    if (visited) {
      result.push(node.val);
    } else {
      // 后序：左右根，入栈顺序相反
      stack.push({ node, visited: true });
      if (node.right) stack.push({ node: node.right, visited: false });
      if (node.left) stack.push({ node: node.left, visited: false });
    }
  }

  return result;
}

层序遍历（BFS）​

访问顺序：[[1], [2, 3], [4, 5, 6]]

基础实现​

function levelOrder<T>(root: TreeNode<T> | null): T[][] {
  if (!root) return [];

  const result: T[][] = [];
  const queue: TreeNode<T>[] = [root];

  while (queue.length) {
    const levelSize = queue.length;
    const currentLevel: T[] = [];

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

      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }

    result.push(currentLevel);
  }

  return result;
}

优化版（避免 shift）​

function levelOrderOptimized<T>(root: TreeNode<T> | null): T[][] {
  if (!root) return [];

  const result: T[][] = [];
  let currentLevel: TreeNode<T>[] = [root];

  while (currentLevel.length) {
    const values: T[] = [];
    const nextLevel: TreeNode<T>[] = [];

    for (const node of currentLevel) {
      values.push(node.val);
      if (node.left) nextLevel.push(node.left);
      if (node.right) nextLevel.push(node.right);
    }

    result.push(values);
    currentLevel = nextLevel;
  }

  return result;
}

锯齿形层序遍历​

function zigzagLevelOrder<T>(root: TreeNode<T> | null): T[][] {
  if (!root) return [];

  const result: T[][] = [];
  const queue: TreeNode<T>[] = [root];
  let leftToRight = true;

  while (queue.length) {
    const levelSize = queue.length;
    const currentLevel: T[] = [];

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;

      if (leftToRight) {
        currentLevel.push(node.val);
      } else {
        currentLevel.unshift(node.val);
      }

      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }

    result.push(currentLevel);
    leftToRight = !leftToRight;
  }

  return result;
}

Morris 遍历（O(1)O(1) 空间）​

Morris 遍历通过修改树结构（线索化）实现 O(1)O(1) 空间复杂度。

Morris 中序遍历​

function morrisInorder<T>(root: TreeNode<T> | null): T[] {
  const result: T[] = [];
  let current = root;

  while (current) {
    if (!current.left) {
      // 没有左子树，访问当前节点，转向右子树
      result.push(current.val);
      current = current.right;
    } else {
      // 找到左子树的最右节点（前驱节点）
      let predecessor = current.left;
      while (predecessor.right && predecessor.right !== current) {
        predecessor = predecessor.right;
      }

      if (!predecessor.right) {
        // 建立线索
        predecessor.right = current;
        current = current.left;
      } else {
        // 恢复树结构
        predecessor.right = null;
        result.push(current.val);
        current = current.right;
      }
    }
  }

  return result;
}

通用遍历模板（统一迭代法）​

type Order = 'pre' | 'in' | 'post';

function traverse<T>(root: TreeNode<T> | null, order: Order): T[] {
  if (!root) return [];

  const result: T[] = [];
  const stack: Array<TreeNode<T> | null> = [root];

  while (stack.length) {
    const node = stack.pop();

    if (!node) {
      // null 标记，下一个节点需要处理
      result.push(stack.pop()!.val);
      continue;
    }

    // 根据遍历顺序，逆序入栈
    if (order === 'pre') {
      // 前序：根左右 → 入栈：右左根
      if (node.right) stack.push(node.right);
      if (node.left) stack.push(node.left);
      stack.push(node);
      stack.push(null); // 标记
    } else if (order === 'in') {
      // 中序：左根右 → 入栈：右根左
      if (node.right) stack.push(node.right);
      stack.push(node);
      stack.push(null);
      if (node.left) stack.push(node.left);
    } else {
      // 后序：左右根 → 入栈：根右左
      stack.push(node);
      stack.push(null);
      if (node.right) stack.push(node.right);
      if (node.left) stack.push(node.left);
    }
  }

  return result;
}

常见面试问题​

Q1: 三种遍历的应用场景？​

答案：

遍历方式应用场景
前序复制树、序列化、构建表达式
中序BST 排序、验证 BST
后序删除树、计算树高度、目录大小
层序按层处理、最短路径、打印树

Q2: 递归和迭代的优缺点？​

答案：

对比项递归迭代
代码简洁度高低
空间复杂度O(h)O(h) 栈空间O(h)O(h) 显式栈
栈溢出风险有无
可控性低高

Q3: 如何根据遍历结果重建二叉树？​

答案：

// 前序 + 中序 → 重建二叉树
function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
  if (!preorder.length) return null;

  const rootVal = preorder[0];
  const root = new TreeNode(rootVal);

  const rootIndex = inorder.indexOf(rootVal);

  root.left = buildTree(
    preorder.slice(1, rootIndex + 1),
    inorder.slice(0, rootIndex)
  );
  root.right = buildTree(
    preorder.slice(rootIndex + 1),
    inorder.slice(rootIndex + 1)
  );

  return root;
}

Q4: 时间复杂度和空间复杂度？​

答案：

方法时间复杂度空间复杂度
递归遍历O(n)O(n)O(h)O(h)，h 为树高
迭代遍历O(n)O(n)O(h)O(h)
MorrisO(n)O(n)O(1)O(1)
层序O(n)O(n)O(w)O(w)，w 为最大宽度

Q5: 如何实现二叉树的层序遍历？变体：锯齿形层序遍历？​

答案：

层序遍历的核心是 BFS + 队列，每次处理一层的所有节点。锯齿形层序遍历（LeetCode 103）是层序遍历（LeetCode 102）的经典变体，只需要在收集每层结果时控制方向。

层序遍历（LeetCode 102）：

function levelOrder(root: TreeNode | null): number[][] {
  if (!root) return [];

  const result: number[][] = [];
  const queue: TreeNode[] = [root];

  while (queue.length) {
    const levelSize = queue.length;
    const currentLevel: number[] = [];

    // 一次处理一整层
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;
      currentLevel.push(node.val);

      // 将下一层节点加入队列
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }

    result.push(currentLevel);
  }

  return result;
}
关键点

levelSize 必须在 for 循环前获取，因为循环体内会往队列中添加下一层节点，queue.length 会变化。

锯齿形层序遍历（LeetCode 103）：

function zigzagLevelOrder(root: TreeNode | null): number[][] {
  if (!root) return [];

  const result: number[][] = [];
  const queue: TreeNode[] = [root];
  let leftToRight = true;

  while (queue.length) {
    const levelSize = queue.length;
    const currentLevel: number[] = [];

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;

      // 根据方向决定插入位置
      if (leftToRight) {
        currentLevel.push(node.val);      // 从左到右：尾部插入
      } else {
        currentLevel.unshift(node.val);   // 从右到左：头部插入
      }

      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }

    result.push(currentLevel);
    leftToRight = !leftToRight; // 每层切换方向
  }

  return result;
}

另一种写法：先正常收集，偶数层 reverse：

function zigzagLevelOrderV2(root: TreeNode | null): number[][] {
  if (!root) return [];

  const result: number[][] = [];
  const queue: TreeNode[] = [root];

  while (queue.length) {
    const levelSize = queue.length;
    const currentLevel: number[] = [];

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;
      currentLevel.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }

    // 偶数层（从 0 开始）反转
    if (result.length % 2 === 1) {
      currentLevel.reverse();
    }

    result.push(currentLevel);
  }

  return result;
}
方法优点缺点
unshift 控制方向不需要额外反转unshift 操作 O(n)O(n)
flag + reverse逻辑更清晰多一次反转操作
双端队列 deque两端操作都是 O(1)O(1)JS 没有原生 deque

Q6: 如何用非递归方式实现前/中/后序遍历？​

答案：

非递归遍历最大的难点在于后序遍历，推荐使用统一模板：栈 + null 标记法，三种遍历方式只需调整入栈顺序即可。

核心思路：当节点第一次出栈时，不访问它，而是将它和一个 null 标记按遍历逆序重新入栈。当出栈元素为 null 时，说明栈顶元素已经就绪，直接弹出并收集。

function universalTraversal(
  root: TreeNode | null,
  order: 'pre' | 'in' | 'post'
): number[] {
  if (!root) return [];

  const result: number[] = [];
  // 栈中 null 作为标记，表示下一个节点待访问
  const stack: Array<TreeNode | null> = [root];

  while (stack.length) {
    const node = stack.pop();

    if (node === null) {
      // null 标记：弹出下一个节点并收集
      result.push(stack.pop()!.val);
      continue;
    }

    // 按遍历顺序的 **逆序** 入栈
    if (order === 'pre') {
      // 前序：根 → 左 → 右，逆序入栈：右 → 左 → 根(null)
      if (node.right) stack.push(node.right);
      if (node.left) stack.push(node.left);
      stack.push(node, null); // null 标记根节点待访问
    } else if (order === 'in') {
      // 中序：左 → 根 → 右，逆序入栈：右 → 根(null) → 左
      if (node.right) stack.push(node.right);
      stack.push(node, null);
      if (node.left) stack.push(node.left);
    } else {
      // 后序：左 → 右 → 根，逆序入栈：根(null) → 右 → 左
      stack.push(node, null);
      if (node.right) stack.push(node.right);
      if (node.left) stack.push(node.left);
    }
  }

  return result;
}

逐一展开各遍历的独立实现：

// 前序遍历（非递归）—— 最简单，直接用栈模拟
function preorderIterative(root: TreeNode | null): number[] {
  if (!root) return [];
  const result: number[] = [];
  const stack: TreeNode[] = [root];

  while (stack.length) {
    const node = stack.pop()!;
    result.push(node.val);
    // 先右后左入栈，出栈时就是先左后右
    if (node.right) stack.push(node.right);
    if (node.left) stack.push(node.left);
  }

  return result;
}

// 中序遍历（非递归）—— 一路向左到底，回溯时访问
function inorderIterative(root: TreeNode | null): number[] {
  const result: number[] = [];
  const stack: TreeNode[] = [];
  let current = root;

  while (current || stack.length) {
    while (current) {
      stack.push(current);
      current = current.left;
    }
    current = stack.pop()!;
    result.push(current.val);
    current = current.right;
  }

  return result;
}

// 后序遍历（非递归）—— 方法 1：反转法
// 前序是 根→左→右，调整为 根→右→左，再 reverse 得到 左→右→根
function postorderIterative(root: TreeNode | null): number[] {
  if (!root) return [];
  const result: number[] = [];
  const stack: TreeNode[] = [root];

  while (stack.length) {
    const node = stack.pop()!;
    result.push(node.val);
    // 注意：先左后右入栈（和前序相反）
    if (node.left) stack.push(node.left);
    if (node.right) stack.push(node.right);
  }

  return result.reverse(); // 反转得到后序
}

// 后序遍历（非递归）—— 方法 2：标记法
function postorderWithFlag(root: TreeNode | null): number[] {
  if (!root) return [];
  const result: number[] = [];
  const stack: Array<{ node: TreeNode; visited: boolean }> = [
    { node: root, visited: false },
  ];

  while (stack.length) {
    const { node, visited } = stack.pop()!;
    if (visited) {
      result.push(node.val);
    } else {
      stack.push({ node, visited: true }); // 标记已访问
      if (node.right) stack.push({ node: node.right, visited: false });
      if (node.left) stack.push({ node: node.left, visited: false });
    }
  }

  return result;
}
总结
  • 前序最简单，栈直接弹出就访问
  • 中序需要"一路向左到底再回溯"的模式
  • 后序最复杂，推荐使用"反转法"或"null 标记统一模板"
  • 统一模板是面试中最推荐的写法，一套代码三种遍历只改入栈顺序

DOM 树遍历​

DOM 树是一种多叉树结构，遍历方式与二叉树类似，但节点可能有多个子节点。

DOM 节点结构​

// DOM 节点的关键属性
interface DOMNode {
  nodeName: string;
  nodeType: number;
  childNodes: NodeList;    // 所有子节点
  children: HTMLCollection; // 仅元素子节点
  firstChild: Node | null;
  lastChild: Node | null;
  nextSibling: Node | null;
  previousSibling: Node | null;
  parentNode: Node | null;
}

深度优先遍历（DFS）​

递归实现​

function traverseDOMRecursive(
  node: Node,
  callback: (node: Node) => void
): void {
  callback(node);

  // 遍历所有子节点
  const children = node.childNodes;
  for (let i = 0; i < children.length; i++) {
    traverseDOMRecursive(children[i], callback);
  }
}

// 仅遍历元素节点
function traverseElementsRecursive(
  element: Element,
  callback: (el: Element) => void
): void {
  callback(element);

  const children = element.children;
  for (let i = 0; i < children.length; i++) {
    traverseElementsRecursive(children[i], callback);
  }
}

// 使用示例
traverseDOMRecursive(document.body, (node) => {
  if (node.nodeType === Node.ELEMENT_NODE) {
    console.log((node as Element).tagName);
  }
});

迭代实现（栈）​

function traverseDOMIterative(
  root: Node,
  callback: (node: Node) => void
): void {
  const stack: Node[] = [root];

  while (stack.length) {
    const node = stack.pop()!;
    callback(node);

    // 子节点逆序入栈，保证正序处理
    const children = node.childNodes;
    for (let i = children.length - 1; i >= 0; i--) {
      stack.push(children[i]);
    }
  }
}

// 仅遍历元素节点
function traverseElementsIterative(
  root: Element,
  callback: (el: Element) => void
): void {
  const stack: Element[] = [root];

  while (stack.length) {
    const element = stack.pop()!;
    callback(element);

    const children = element.children;
    for (let i = children.length - 1; i >= 0; i--) {
      stack.push(children[i]);
    }
  }
}

广度优先遍历（BFS）​

function traverseDOMBFS(
  root: Node,
  callback: (node: Node, depth: number) => void
): void {
  const queue: Array<{ node: Node; depth: number }> = [{ node: root, depth: 0 }];

  while (queue.length) {
    const { node, depth } = queue.shift()!;
    callback(node, depth);

    const children = node.childNodes;
    for (let i = 0; i < children.length; i++) {
      queue.push({ node: children[i], depth: depth + 1 });
    }
  }
}

// 仅遍历元素节点，按层返回
function traverseElementsByLevel(root: Element): Element[][] {
  const result: Element[][] = [];
  const queue: Element[] = [root];

  while (queue.length) {
    const levelSize = queue.length;
    const level: Element[] = [];

    for (let i = 0; i < levelSize; i++) {
      const element = queue.shift()!;
      level.push(element);

      const children = element.children;
      for (let j = 0; j < children.length; j++) {
        queue.push(children[j]);
      }
    }

    result.push(level);
  }

  return result;
}

使用 TreeWalker API​

TreeWalker 是浏览器原生的 DOM 遍历 API，性能更好。

function traverseWithTreeWalker(
  root: Node,
  whatToShow: number = NodeFilter.SHOW_ELEMENT
): Element[] {
  const elements: Element[] = [];

  const walker = document.createTreeWalker(
    root,
    whatToShow,
    null  // 可传入过滤函数
  );

  let node = walker.currentNode;
  while (node) {
    if (node.nodeType === Node.ELEMENT_NODE) {
      elements.push(node as Element);
    }
    node = walker.nextNode()!;
    if (!node) break;
  }

  return elements;
}

// 带过滤器的 TreeWalker
function findElementsByClass(root: Element, className: string): Element[] {
  const elements: Element[] = [];

  const walker = document.createTreeWalker(
    root,
    NodeFilter.SHOW_ELEMENT,
    {
      acceptNode(node: Element) {
        return node.classList.contains(className)
          ? NodeFilter.FILTER_ACCEPT
          : NodeFilter.FILTER_SKIP;
      }
    }
  );

  let node: Element | null;
  while ((node = walker.nextNode() as Element | null)) {
    elements.push(node);
  }

  return elements;
}

使用 NodeIterator API​

function iterateNodes(
  root: Node,
  whatToShow: number = NodeFilter.SHOW_ALL
): Node[] {
  const nodes: Node[] = [];

  const iterator = document.createNodeIterator(
    root,
    whatToShow,
    null
  );

  let node: Node | null;
  while ((node = iterator.nextNode())) {
    nodes.push(node);
  }

  return nodes;
}

实际应用示例​

// 1. 获取所有文本内容
function getAllTextContent(root: Element): string {
  const texts: string[] = [];

  traverseDOMIterative(root, (node) => {
    if (node.nodeType === Node.TEXT_NODE) {
      const text = node.textContent?.trim();
      if (text) texts.push(text);
    }
  });

  return texts.join(' ');
}

// 2. 统计元素个数
function countElements(root: Element): Map<string, number> {
  const counts = new Map<string, number>();

  traverseElementsIterative(root, (el) => {
    const tag = el.tagName.toLowerCase();
    counts.set(tag, (counts.get(tag) || 0) + 1);
  });

  return counts;
}

// 3. 查找最大嵌套深度
function getMaxDepth(root: Element): number {
  let maxDepth = 0;

  traverseDOMBFS(root, (_, depth) => {
    maxDepth = Math.max(maxDepth, depth);
  });

  return maxDepth;
}

// 4. 序列化 DOM 结构
interface DOMStructure {
  tag: string;
  children: DOMStructure[];
}

function serializeDOMStructure(element: Element): DOMStructure {
  const children: DOMStructure[] = [];

  for (let i = 0; i < element.children.length; i++) {
    children.push(serializeDOMStructure(element.children[i]));
  }

  return {
    tag: element.tagName.toLowerCase(),
    children
  };
}

DOM 遍历性能对比​

方法优点缺点适用场景
递归 DFS代码简洁深层嵌套栈溢出一般场景
迭代 DFS无栈溢出代码稍复杂深层 DOM
BFS按层处理内存占用高层级操作
TreeWalker原生 API、性能好兼容性生产环境
NodeIterator简单顺序遍历功能单一简单遍历

相关链接​