Question

如果有一棵二叉树的中序遍历是BAC,那么它的先序遍历不可能是？

如果有一棵二叉树的中序遍历是BAC,那么它的先序遍历不可能是？
A.ABC
B.CBA
C.ACB
D.BAC
请附上二叉树的图片和方法！谢谢！

Answer 1

按照二叉树遍历的特点，将各个答案去还原就可以得到：

A、

B、

D、

C、答案出现矛盾

Answer 2

先序遍历的操作为：先访问根结点，再先序遍历左子树，最后先序遍历右子树。

中序遍历操作为：先中序遍历左子树，访问根结点，再中序遍历右子树。

所以中序遍历是BAC的话.原二叉树结构可能是：
1. A
/ \
B C
则其先序遍历为ABC，则答案A正确

2. C
/
B
\
A
则其先序遍历为CBA，可以验证其中序遍历，（因为B上无右子树）先读左子树B，因为B上仍有右子树子树，所以要在读A，最后读根结点C，其中序遍历就为BAC。所以答案B正确。

3. B
\
A
\
C
易得其先序遍历为BAC，验证方法同理2，所以D答案也正确。

最后可以排除C答案。