已知⼆叉树的先序遍历和中序遍历画出该⼆叉树
对⼀棵⼆叉树进⾏遍历，我们可以采取3中顺序进⾏遍历，分别是前序遍历、中序遍历和后序遍历。
这三种⽅式是以访问⽗节点的顺序来进⾏命名的。
假设⽗节点是N，左节点是L，右节点是R，那么对应的访问遍历顺序如下：
前序遍历    N－>L－>R
中序遍历    L－>N－>R
后序遍历    L－>R－>N
所以，对于以下这棵树，三种遍历⽅式的结果是
前序遍历    ABCDEF
中序遍历    CBDAEF
后序遍历    CDBFEA
已知⼆叉树的前序遍历和中序遍历，如何得到它的后序遍历
其实，只要知道其中任意两种遍历的顺序，我们就可以推断出剩下的⼀种遍历⽅式的顺序，这⾥我们只是以：
知道前序遍历和中序遍历，推断后序遍历作为例⼦，其他组合⽅式原理是⼀样的。要完成这个任务，我们⾸先要利⽤以下⼏个特性：
特性A，对于前序遍历，第⼀个肯定是根节点；
特性B，对于后序遍历，最后⼀个肯定是根节点；
特性C，利⽤前序或后序遍历，确定根节点，在中序遍历中，根节点的两边就可以分出左⼦树和右⼦树；
特性D，对左⼦树和右⼦树分别做前⾯3点的分析和拆分，相当于做递归，我们就可以重建出完整的⼆叉树；
我们以⼀个例⼦做⼀下这个过程，假设：
前序遍历的顺序是: CABGHEDF
中序遍历的顺序是: GHBACDEF
第⼀步，我们根据特性A，可以得知根节点是C，然后，根据特性C，我们知道左⼦树是：GHBA，右⼦树是：DEF。
C
/    \
GHBA  DEF
第⼆步，取出左⼦树，左⼦树的前序遍历是：ABGH，中序遍历是：GHBA，根据特性A和C，得出左⼦树的⽗节点是A，并且A没有右⼦树。
C
/    \
A    DEF
/
GBH
第三步，使⽤同样的⽅法，前序是BGH，中序是GHB，得出⽗节点是B，GH是左⼦树，没有右⼦树。
C
/    \
A    DEF
/
B
/
GH
第四步，前序是GH, 中序是GH, 所以 G是⽗节点,  H是右⼦树,  没有左⼦树.
C
/    \
先序中序后序遍历二叉树A    DEF
/
B
/
G
\
H
第四步，回到右⼦树，它的前序是EDF，中序是DEF，依然根据特性A和C，得出⽗节点是E，左右节点是D和F。
C
/    \
A        E
/          /    \
B          D      F
/
G
\
H
到此，我们得到了这棵完整的⼆叉树，因此，它的后序遍历就是 : HGBADFEC

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。