如何实现二叉树的非递归遍历?
参考答案
前序(根左右)
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 输出一层。
核心:用显式栈模拟递归的调用栈。