用前序遍历结果去分割中序遍历结果,还原二叉树,然后再依此写出后序遍历结果。
前序遍历结果第一位为E,说明根节点为E,以E分割中序遍历结果,得左子树为ABCD,右子树为FGHIJK:
E
/ \
ABCD FGHIJK
前序遍历第二位为B,说明B为左子树父节点,以B分割中序遍历,得A为左子树,CD为右子树:
E
/ \
B FGHIJK
/ \
A CD
前序遍历第三位为A,说明A为左节点,但2中B的左子树只有A,所以无需再分割;
前序遍历第四位为D,说明D为C的父节点,据此分割中序遍历,得C为D的左子树:
E
/ \
B FGHIJK
/ \
A D
/
C
前序遍历第五位为C,同3,无需再分割;
前序遍历第六位为F,以F分割中序遍历,得F左子树为空,右子树为GHIJK:
E
/ \
B F
/ \ \
A D GHIJK
/
C
前序遍历第七位为H,以H分割中序遍历,得H左子树为G,右子树为IJK:
E
/ \
B F
/ \ \
A D H
/ / \
C G IJK
8.前序遍历第八位为G,同3,无需再分割;
9.前序遍历第九位为I,以I分割中序遍历,得I左子树为空,右子树为JK:
E
/ \
B F
/ \ \
A D H
/ / \
C G I
\
JK
10.前序遍历第十位为K,以K分割中序遍历,得K左子树为J,右子树为空。到此,二叉树被完全还原:
E
/ \
B F
/ \ \
A D H
/ / \
C G I
\
K
/
J
11.根据还原出的二叉树写出后序遍历:ACDBGJKIHFE