Question

有一棵二叉树的先序和中序遍历分别如下，画出该二叉树（描述生成过程），并写出其后序遍历序列.

有一棵二叉树的先序和中序遍历分别如下，画出该二叉树（描述生成过程），并写出其后序遍历序列.
先序：A B C D E F G H I J
中序：C B E D A G H F J I

Answer 1

先序：A B C D E F G H I J
中序：C B E D A G H F J I

确定根是A，C B E D在A的左子树上，G H F J I在A的右子树上。

先序：B C D E
中序：C B E D
确定B是根，C是B的左孩子，E D在B的右子树上。

先序：D E
中序：E D
确定D是根，E是D的左孩子。

先序：F G H I J
中序：G H F J I
确定F是根，G H在F的左子树上，J I在F的右子树上。

先序：G H
中序：G H
确定G是根，H是G的右孩子。

先序：I J
中序：J I
确定I是根，J是I的左孩子。

综合起来，树的结构如下所示：
A
B F
C D G I
E H J

后序遍历序列：C E D B H G J I F A