二叉树遍历：前序、中序、后序

问题

实现二叉树的前序、中序、后序遍历，分别用递归和迭代两种方式。

解答

二叉树节点定义

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

前序遍历（根 → 左 → 右）

// 递归
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(); // 反转得到：左 → 右 → 根
}

测试

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

const root = new TreeNode(1,
  new TreeNode(2, new TreeNode(4), new TreeNode(5)),
  new TreeNode(3)
);

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]

关键点

• 前序：根左右；中序：左根右；后序：左右根
• 递归写法简单，改变 push 位置即可切换遍历方式
• 前序迭代：栈中先压右再压左，保证左先出
• 中序迭代：不断向左走并压栈，弹出后转向右子树
• 后序迭代：可用「根右左 + 反转」的技巧简化实现