二叉树遍历算法详解 — 何福永 HeStudy

二叉树基础

二叉树是一种重要的数据结构。它的每个节点最多有两个子节点，通常称为左子树和右子树。

节点定义

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

深度优先搜索（DFS）

1. 前序遍历

访问顺序：根节点 → 左子树 → 右子树

递归实现

function preorderTraversal(root) {
  const result = [];

  function traverse(node) {
    if (!node) return;

    result.push(node.val); // 访问根节点
    traverse(node.left); // 遍历左子树
    traverse(node.right); // 遍历右子树
  }

  traverse(root);
  return result;
}

迭代实现

用栈模拟递归过程：

function preorderTraversal(root) {
  if (!root) return [];

  const result = [];
  const stack = [root];

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

    // 先压右节点，再压左节点，因为栈是后进先出
    if (node.right) stack.push(node.right);
    if (node.left) stack.push(node.left);
  }

  return result;
}

2. 中序遍历

访问顺序：左子树 → 根节点 → 右子树

对于二叉搜索树，中序遍历会得到升序结果。

递归实现

function inorderTraversal(root) {
  const result = [];

  function traverse(node) {
    if (!node) return;

    traverse(node.left); // 遍历左子树
    result.push(node.val); // 访问根节点
    traverse(node.right); // 遍历右子树
  }

  traverse(root);
  return result;
}

迭代实现

function inorderTraversal(root) {
  const result = [];
  const stack = [];
  let current = root;

  while (current || stack.length > 0) {
    while (current) {
      stack.push(current);
      current = current.left;
    }

    current = stack.pop();
    result.push(current.val);
    current = current.right;
  }

  return result;
}

3. 后序遍历

访问顺序：左子树 → 右子树 → 根节点

递归实现

function postorderTraversal(root) {
  const result = [];

  function traverse(node) {
    if (!node) return;

    traverse(node.left); // 遍历左子树
    traverse(node.right); // 遍历右子树
    result.push(node.val); // 访问根节点
  }

  traverse(root);
  return result;
}

迭代实现

function postorderTraversal(root) {
  if (!root) return [];

  const result = [];
  const stack = [root];

  while (stack.length > 0) {
    const node = stack.pop();
    result.unshift(node.val);

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

  return result;
}

广度优先搜索（BFS）

层序遍历

层序遍历按层访问节点，通常用队列实现。

function levelOrder(root) {
  if (!root) return [];

  const result = [];
  const queue = [root];

  while (queue.length > 0) {
    const levelSize = queue.length;
    const currentLevel = [];

    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;
}

锯齿形层序遍历

function zigzagLevelOrder(root) {
  if (!root) return [];

  const result = [];
  const queue = [root];
  let leftToRight = true;

  while (queue.length > 0) {
    const levelSize = queue.length;
    const currentLevel = [];

    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;
}

实际应用

1. 二叉树最大深度

function maxDepth(root) {
  if (!root) return 0;

  return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

2. 判断平衡二叉树

function isBalanced(root) {
  function height(node) {
    if (!node) return 0;

    const leftHeight = height(node.left);
    if (leftHeight === -1) return -1;

    const rightHeight = height(node.right);
    if (rightHeight === -1) return -1;

    if (Math.abs(leftHeight - rightHeight) > 1) {
      return -1;
    }

    return Math.max(leftHeight, rightHeight) + 1;
  }

  return height(root) !== -1;
}

3. 二叉树最近公共祖先

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;
}

时间与空间复杂度

遍历方式	时间复杂度	最坏空间复杂度
前序遍历	O(n)	O(n)
中序遍历	O(n)	O(n)
后序遍历	O(n)	O(n)
层序遍历	O(n)	O(n)

面试提示

递归 vs 迭代：递归更简洁，但深树可能导致调用栈溢出；迭代用显式栈，更适合大数据量。
空间优化：Morris Traversal 可以做到 O(1) 额外空间。
边界情况：空节点、单节点、只有左子树或右子树都要覆盖。
灵活迁移：很多树题本质上都可以转化为遍历问题。

总结

二叉树遍历是基础但非常重要的算法。掌握 DFS 与 BFS、递归与迭代两套写法，是解决复杂树问题的前提。