Question

已知一棵二叉树的先序遍历序列为ABCDEFGHIJ，中序遍历序列为CBDEAFHIGJ.

已知一棵二叉树的先序遍历序列为ABCDEFGHIJ，中序遍历序列为CBDEAFHIGJ.试构造这棵二叉树，要求写出构造过程步骤

• 你的回答被采纳后将获得：
• 系统奖励15（财富值+成长值）+难题奖励10（财富值+成长值）+提问者悬赏20（财富值+成长值）

Answer 1

先看先序，其第一个为树的根，先序遍历是先根再左子树最后右子树，第一个肯定是树的根，先画A，A再中序遍历中左右都有，说明A有左子树也有右子树。

A
/ \
然后看先序第一个值是B，在中序中为A的前面，所以B是A的左子树
A
/ \
B
继续看先序，接下来是C、D，C再中序中再B的前面，所以C是B的左子树，D在B后面，D是B的右子树。
A
/ \
B
/ \
C D
接下来是E，E在中序是在D后面A前面，所以E是D的右子树
A
/ \
B
/ \
C D
\
E
接着先序中是F，F在中序为A后面，是A的右子树
A
/ \
B F
/ \
C D
\
E
中序中 A 与F之间没有，说明F没有左子树，只有右子树.如上面方法继续分析GHIJ，最终二叉树如下：
A
/ \
B F
/ \ \
C D G
\ / \
E H J
\
I

Answer 2

引用wzhappysnail的回答：
先看先序，其第一个为树的根，先序遍历是先根再左子树最后右子树，第一个肯定是树的根，先画A，A再中序遍历中左右都有，说明A有左子树也有右子树。

A
/ \
然后看先序第一个值是B，在中序中为A的前面，所以B是A的左子树
A
/ \
B
继续看先序，接下来是C、D，C再中序中再B的前面，所以C是B的左子树，D在B后面，D是B的右子树。
A
/ \
B
/ \
C D
接下来是E，E在中序是在D后面A前面，所以E是D的右子树
A
/ \
B
/ \
C D
\
E
接着先序中是F，F在中序为A后面，是A的右子树
A
/ \
B F
/ \
C D
\
E
中序中 A 与F之间没有，说明F没有左子树，只有右子树.如上面方法继续分析GHIJ，最终二叉树如下：
A
/ \
B F
/ \ \
C D G
\ / \
E H J
\
I

1 答案不唯一
2 e位置错误