← 返回完整题库
JavaScript困难

如何实现二叉树的非递归遍历?

参考答案

前序(根左右)

const stack = [root], out = [];
while (stack.length) {
  const n = stack.pop(); out.push(n.val);
  if (n.right) stack.push(n.right);   // 先压右
  if (n.left) stack.push(n.left);
}

中序(左根右)

const stack = []; let cur = root;
while (cur || stack.length) {
  while (cur) { stack.push(cur); cur = cur.left; }
  cur = stack.pop(); out.push(cur.val); cur = cur.right;
}

后序

用"根右左"的变体再整体反转;或用双栈;或记录 lastVisited 标记。

层序

队列 BFS,每层记录 size 输出一层。

核心:用显式栈模拟递归的调用栈。

本题来自 计算机知识面试题库,共 921 道题。