二叉树遍历

问题

实现二叉树的四种遍历方式：前序、中序、后序、层序。

解答

二叉树节点定义

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

前序遍历（根 → 左 → 右）

// 递归
function preorderRecursive(root) {
  const result = [];
  
  function traverse(node) {
    if (!node) return;
    result.push(node.val);    // 先访问根
    traverse(node.left);       // 再访问左子树
    traverse(node.right);      // 最后访问右子树
  }
  
  traverse(root);
  return result;
}

// 迭代
function preorderIterative(root) {
  if (!root) return [];
  
  const result = [];
  const stack = [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 inorderRecursive(root) {
  const result = [];
  
  function traverse(node) {
    if (!node) return;
    traverse(node.left);       // 先访问左子树
    result.push(node.val);     // 再访问根
    traverse(node.right);      // 最后访问右子树
  }
  
  traverse(root);
  return result;
}

// 迭代
function inorderIterative(root) {
  const result = [];
  const stack = [];
  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;
}

后序遍历（左 → 右 → 根）

// 递归
function postorderRecursive(root) {
  const result = [];
  
  function traverse(node) {
    if (!node) return;
    traverse(node.left);       // 先访问左子树
    traverse(node.right);      // 再访问右子树
    result.push(node.val);     // 最后访问根
  }
  
  traverse(root);
  return result;
}

// 迭代（前序的变体：根右左 → 反转得到左右根）
function postorderIterative(root) {
  if (!root) return [];
  
  const result = [];
  const stack = [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(); // 反转得到左右根
}

层序遍历（BFS）

function levelOrder(root) {
  if (!root) return [];
  
  const result = [];
  const queue = [root];
  
  while (queue.length) {
    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;
}

测试

//       1
//      / \
//     2   3
//    / \
//   4   5

const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

console.log(preorderRecursive(root));   // [1, 2, 4, 5, 3]
console.log(inorderRecursive(root));    // [4, 2, 5, 1, 3]
console.log(postorderRecursive(root));  // [4, 5, 2, 3, 1]
console.log(levelOrder(root));          // [[1], [2, 3], [4, 5]]

关键点

• 前/中/后序的区别在于根节点的访问时机：前序先访问根，中序中间访问根，后序最后访问根
• 递归写法简单直观，但有栈溢出风险；迭代用显式栈模拟递归过程
• 层序遍历用队列实现 BFS，记录每层节点数来区分层级
• 后序迭代可以用前序变体（根右左）再反转得到
• 中序遍历的迭代写法需要先一路向左，再回溯处理右子树