给定一棵树的先根遍历序列和后根遍历序列，能否唯一确定一棵树？若能，请举例说明；若不能，请给出反例。

[tag_link]

参考答案

有序树且结点标识互异时，孩子兄弟二叉树的先序等于原树先根，中序等于原树后根；先序与中序可唯一重建二叉树，故能唯一确定。若是一般二叉树只给先序与后序，或允许重复标识，则不成立：例如只有 A、B 两个结点时，B 作 A 的左孩子或右孩子，先序均为 AB、后序均为 BA。

推导过程

孩子兄弟转换把第一个孩子连为 left、下一个兄弟连为 right；递归展开可得先序访问根及孩子链、后序访问孩子后根与兄弟链，恰对应原树先根/后根。互异标识保证中序根划分唯一。

复杂度与边界

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

易错点

不要把一般二叉树的先序+后序误当作总能唯一重建；本题能唯一确定依赖转换后得到的是先序+中序且结点标识互异。

评分要点

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