Skip to content
AI Learning Hub

二叉树

🌲 二叉树遍历

Section titled “🌲 二叉树遍历”

理解四种遍历方式，是掌握树结构的关键。

🌲二叉树遍历

中序遍历顺序: 左 → 根 → 右
应用: BST 有序输出
遍历顺序:
[...]
// 中序遍历 (左 → 根 → 右)
function inorder(node) {
if (!node) return;
inorder(node.left);
visit(node); // 中间访问根
inorder(node.right);
}
📊 复杂度
时间: O(n) - 每个节点访问一次
空间: O(h)(递归栈深度)
记忆口诀:
前序: 根左右 (VLR)
中序: 左根右 (LVR)
后序: 左右根 (LRV)

🎯 遍历方式对比

Section titled “🎯 遍历方式对比”
遍历顺序记忆口诀典型应用
前序根→左→右VLR (Visit first)复制树、序列化
中序左→根→右LVR (Visit middle)BST 有序输出
后序左→右→根LRV (Visit last)删除树、后缀表达式
层序按层扫描BFS按层打印、最短路径

📝 代码实现

Section titled “📝 代码实现”

递归版本 (DFS)

Section titled “递归版本 (DFS)”
// 前序遍历
function preorder(node) {
  if (!node) return;
  visit(node);         // 先访问根
  preorder(node.left);
  preorder(node.right);
}


// 中序遍历
function inorder(node) {
  if (!node) return;
  inorder(node.left);
  visit(node);         // 中间访问根
  inorder(node.right);
}


// 后序遍历
function postorder(node) {
  if (!node) return;
  postorder(node.left);
  postorder(node.right);
  visit(node);         // 最后访问根
}

迭代版本

Section titled “迭代版本”
// 前序遍历 - 栈
function preorderIterative(root) {
  const result = [];
  const stack = [root];


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


    result.push(node.val);   // 访问
    stack.push(node.right);  // 先右后左 (栈是 LIFO)
    stack.push(node.left);
  }
  return result;
}


// 层序遍历 - 队列
function levelOrder(root) {
  const result = [];
  const queue = [root];


  while (queue.length) {
    const node = queue.shift();
    if (!node) continue;


    result.push(node.val);
    queue.push(node.left);
    queue.push(node.right);
  }
  return result;
}

📊 复杂度

Section titled “📊 复杂度”
指标值说明
时间O(n)每个节点访问一次
空间 (递归)O(h)h 是树高，最坏 O(n)
空间 (层序)O(w)w 是最大宽度，最坏 O(n)

🔗 相关知识

Section titled “🔗 相关知识”