二叉树深度遍历（DFS）

问题

二叉树的深度优先遍历（DFS）是一种重要的树遍历算法，需要实现三种遍历方式：

1. 前序遍历（Pre-order）：根节点 → 左子树 → 右子树
2. 中序遍历（In-order）：左子树 → 根节点 → 右子树
3. 后序遍历（Post-order）：左子树 → 右子树 → 根节点

每种遍历方式都需要提供递归和迭代两种实现方法。

解答

// 定义二叉树节点
class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

// 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 preorderTraversalIterative(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 inorderTraversalIterative(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 postorderTraversalIterative(root) {
  if (!root) return [];
  
  const result = [];
  const stack1 = [root];
  const stack2 = [];
  
  // 第一个栈：根 → 右 → 左（前序遍历的变形）
  while (stack1.length > 0) {
    const node = stack1.pop();
    stack2.push(node);
    
    // 先压入左子节点，再压入右子节点
    if (node.left) stack1.push(node.left);
    if (node.right) stack1.push(node.right);
  }
  
  // 第二个栈弹出，得到后序遍历结果
  while (stack2.length > 0) {
    result.push(stack2.pop().val);
  }
  
  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('前序遍历（递归）:', preorderTraversal(root));
// 输出: [1, 2, 4, 5, 3]

console.log('前序遍历（迭代）:', preorderTraversalIterative(root));
// 输出: [1, 2, 4, 5, 3]

// 中序遍历
console.log('中序遍历（递归）:', inorderTraversal(root));
// 输出: [4, 2, 5, 1, 3]

console.log('中序遍历（迭代）:', inorderTraversalIterative(root));
// 输出: [4, 2, 5, 1, 3]

// 后序遍历
console.log('后序遍历（递归）:', postorderTraversal(root));
// 输出: [4, 5, 2, 3, 1]

console.log('后序遍历（迭代）:', postorderTraversalIterative(root));
// 输出: [4, 5, 2, 3, 1]

关键点

• 递归实现：代码简洁直观，但可能存在栈溢出风险（深度过大时）

  • 递归终止条件：节点为空时返回
  • 按照遍历顺序调整访问节点和递归调用的位置

• 迭代实现：使用显式栈模拟递归过程，避免栈溢出

  • 前序遍历：直接用栈，注意右子节点先入栈
  • 中序遍历：先一路向左压栈，再弹出访问，最后转向右子树
  • 后序遍历：使用双栈或单栈+标记法

• 时间复杂度：O(n)，每个节点访问一次

• 空间复杂度：O(h)，h 为树的高度（递归栈或显式栈的空间）

• 应用场景：

  • 前序遍历：复制树、序列化树
  • 中序遍历：二叉搜索树的有序输出
  • 后序遍历：删除树、计算目录大小