5.3.1 遍历与由序列重建

先序是根-左-右，中序是左-根-右，后序是左-右-根，层序按队列逐层访问。递归遍历差别只在访问根的时机。具有互异关键字时，先序+中序或后序+中序能唯一确定二叉树；仅先序+后序通常不能。

手工推演

先序 ABDECF、中序 DBEACF：先序首 A 是根，中序将其分成 DBE 与 CF；左子树先序取接下来的 BDE，根 B，再分出 D、E；右子树根 C、右孩子 F。得到后序 DEBFCA。

结构与代码

void pre(Node*r){if(!r)return;visit(r);pre(r->l);pre(r->r);}

非递归先序用栈：弹出根访问，先压右再压左；层序用队列。每结点访问一次，时间 $O(n)$，辅助空间取决于高度或最大层宽。

错解反馈

重建时不按中序左右段长度切分另一序列；有重复值仍声称唯一；非递归栈压左再压右导致访问顺序反了。

迁移练习

先序 12435、中序 42135，重建并写后序。答案 42531。独立验收：每次递归都标出根、左右区间。