给定二叉树先序序列 ABDEHCFIMGJKL、中序序列 DBHEAIMFCGKLJ，完整重建二叉树并转换为森林，写出二叉树边、森林父子边以及先根和后根序列。

[tag_link]

参考答案

二叉树边为 A-L-B、A-R-C、B-L-D、B-R-E、E-L-H、C-L-F、C-R-G、F-L-I、I-R-M、G-R-J、J-L-K、K-R-L。转换森林的根链为 A→C→G→J，父子边为 A-B、A-E、B-D、E-H、C-F、F-I、F-M、J-K、J-L；森林先根为 ABDEHCFIMGJKL，后根为 DBHEAIMFCGKLJ。

推导过程

先序首项 A 为根；在中序 DBHE|A|IMFCGKLJ 中划分左右子树，递归得到 B/E/H 与 C/F/G/J，再按孩子兄弟规则将右链解释为兄弟链。

复杂度与边界

时间 O(n)，递归栈 O(h_cs)，最坏 O(n)；空输入与单点边界已说明。

易错点

右指针在孩子兄弟表示中是兄弟而非右孩子；森林根链也不能误报成同一棵树的父子链。

评分要点

• 写出核心结构对应关系或伪代码
• 给出正确性理由
• 给出复杂度与边界