NOIP 提高组初赛 · NOIP 2008 提高组初赛试题第 16 题

选择题 · 答案 ABD · 考点：二叉树的遍历

题目

二叉树 $T$，已知其先根遍历是 $\texttt{1 2 4 3 5 7 6}$（数字为结点的编号，以下同），后根遍历是 $\texttt{4 2 7 5 6 3 1}$，则该二叉树的可能的中根遍历是（）。

答案：ABD

二叉树的遍历

先序 1 2 4 3 5 7 6，后序 4 2 7 5 6 3 1：可能存在多种中序形态。

先序+后序不能唯一确定二叉树，需分别验证左、右子树。

二叉树遍历

先序: 1 2 4 3 5 7 6 后序: 4 2 7 5 6 3 1

根=1。2和4在左子树，3,5,7,6在右子树。

右子树分析：先序3 5 7 6，后序7 5 6 3。根=3。

多种形态导致多种中序。

正确答案：A、B、D

在 OI伴学里做这道题

登录后可计时作答、查看完整六段式解析，并按你的错题自动生成同类练习。