preorder/inorder 转 postorder 为何未通过 eLab Logical T4？

这份实现对题目规定的有效输入是正确的

满足以下条件时，代码会输出正确的 postorder：

• 1 ≤ n ≤ 100000；
• 节点编号为 1..n，且各不相同；
• preorder 和 inorder 来自同一棵二叉树；
• 运行环境提供足够的时间和内存。

单节点、完全左偏、完全右偏以及高度不平衡的树，都不会使遍历逻辑出错。即使 n = 100000，这里的显式栈也不会越界。

目前可以确认的输出细节是，最后一个节点后面有空格。它是否会导致 Logical T4 失败，取决于 checker 的比较规则。仅凭 Logical T4 : FAIL，无法得知隐藏输入和具体失败类型，也没有依据认定 eLab 的数据或 checker 有问题。

栈状态和子树边界没有明显错误

每个 F 保存处理一棵子树所需的信息：

typedef struct{int l,r,s,v,p;}F;

[l, r] 是当前子树在 inorder 中的区间，v 是根节点，p 是根在 inorder 中的位置。s 记录处理进度：

输出顺序为：

左子树 → 右子树 → 根

对于有效输入，首次进入一个非空区间时，pre[pi] 就是该子树的根。它在 inorder 中的位置必然满足：

f->l <= f->p && f->p <= f->r

左右子树分别使用以下区间：

[f->l, f->p - 1]
[f->p + 1, f->r]

遇到空区间时，程序直接弹栈，不消耗 preorder 元素：

if(f->l>f->r){top--;continue;}

因此，每个节点恰好读取一次、输出一次。遍历完成后，pi 应为 n + 1。

压栈时使用 f 没有问题

这两行代码也不会使 f 失效：

F *f=&st[top-1];
st[top++]=(F){f->l,f->p-1,0,0,0};

f 指向原来的栈顶，新帧写入下一个数组元素。st 是固定数组，压栈时不会重新分配内存，f 仍指向原来的位置。

赋值两侧的求值顺序不必固定，但右侧只访问 f 指向的成员，没有再次读取或修改 top，所以这里的 top++ 不会引起未定义行为。

n = 100000 时，栈容量足够

显式栈保存的是当前处理路径上的帧，不会同时保存所有左右子树。

树高 h 按路径上的节点数计算时，最多需要：

h 个非空子树帧 + 1 个空子树帧

由于 h ≤ n，同时在栈中的帧数最多为 n + 1。原代码分配了：

static F st[MAXN*2];

这个数组有 200000 个元素，足以容纳最多 100001 个帧。

完全左偏时，程序不断压入左子树；完全右偏时，程序先弹出空左子树，再压入右子树。两种情况都不会超过这个上限，也不需要深度为 n 的递归调用栈。

算法的时间复杂度和额外空间复杂度都是 O(n)。在 int 为 4 字节且 sizeof(F) == 20 的环境中，三个静态数组合计约占 4.8 MB，是否符合要求还要核对题目的实际内存上限。

平台的 Cyclomatic Complexity、Token Count 和 NLOC 检查不验证遍历结果，也不能保证运行时间和内存占用符合限制。

先消除末尾空格，再核对失败类型

原输出语句是：

printf("%d ",f->v);

每行最后一个数字后也会输出空格。按整数或空白分隔比较的 checker 通常会忽略它，逐字节比较的 checker 则可能判错。题目信息没有说明 eLab 使用哪种规则。

可以先在 main 的变量声明处增加：

int first = 1;

将原来的输出分支替换为：

}else{
    if(!first) putchar(' ');
    printf("%d",f->v);
    first=0;
    top--;
}

保留循环结束后的：

printf("\n");

这样就只在相邻数字之间输出空格。题目强制要求的：

for(i=1;i<=n;i++)

不需要改动。

这项修改可以排除末尾空格的影响，能否通过 T4 仍需验证。修改后也要重新检查 Token Count、NLOC 等平台限制。

如果平台提供了具体的失败类型，可以据此排查：

如果只显示 FAIL，就无法判断是否为算法答案错误。

用针对性测试继续定位

先核对以下小用例：

最大规模测试可以将两种偏斜结构扩展到 n = 100000。另外，还应构造左右子树交替出现的树，检查父帧从 s == 1 恢复执行的情况。

更有效的验证方法是随机生成一棵小树，再生成它的 preorder、inorder 和作为基准的 postorder，与提交程序的输出比较。不要直接随机打乱两个排列：即使它们都包含 1..n，也不一定是有效的遍历序列对。

本地调试时，可以加入断言，检查读取根节点时的状态。先引入：

#include <assert.h>

将 s == 0 分支中读取根的部分临时改为：

assert(pi <= n);
f->v = pre[pi++];

assert(1 <= f->v && f->v <= n);
f->p = pos[f->v];

assert(f->l <= f->p && f->p <= f->r);
f->s = 1;

遍历结束后检查：

assert(pi == n + 1);

这些断言可以帮助定位输入与区间状态不一致的位置，有效输入不应触发它们。调试代码是否符合平台的静态检查要求，需要另行核对。

什么时候才有依据怀疑评测数据

还要核对完整题面，确认是否存在多组测试，以及节点编号是否确实为 1..n。原程序只处理一组输入，并直接把节点值用作 pos[] 的下标，这与当前给出的要求一致。

如果实际要求不同，就按题面调整。不要为了猜测 T4 的输入，擅自改成“首项为测试组数”或“读取到 EOF”。

确认输入协议、资源限制、输出格式和实际提交代码都与要求一致后，再向课程维护者请求核查 T4。核查时最有帮助的是该测试的具体失败类型、首个输出差异，或可复现的输入。

备注：内容仅供参考。