怎样用显式栈实现树的前序遍历？

前序遍历先访问当前节点，再按顺序遍历它的子树。递归写法直观，但很深的树可能超出调用栈；显式栈可以把待访问节点放到堆上维护。

下面的教学实现约定节点有 value 和可选 children 数组，输入是无环树，不在遍历时修改结构。空根返回空数组；子节点反向入栈，弹出时才会保持从左到右顺序。

JavaScript

function preorder(root) {
  if (root == null) return [];
  const stack = [root];
  const values = [];
  while (stack.length > 0) {
    const node = stack.pop();
    values.push(node.value);
    const children = node.children ?? [];
    for (let index = children.length - 1; index >= 0; index--) {
      stack.push(children[index]);
    }
  }
  return values;
}

对 n 个节点，这种遍历访问每个节点一次，时间为 O(n)。本实现保存结果需要 O(n) 空间，待访问栈在宽树下也可能达到 O(n)，不能笼统说所有非递归 DFS 都只有 O(树高) 空间。

它不是通用图遍历：有环或共享子节点时，需要先决定去重规则，再加入访问记录。参考文档解释栈使用的数组 API；遍历代码为本项目编写，并用顺序、空树和深树用例验证。