Question

若二叉树的先序和中序遍历结果

若二叉树的先序和中序遍历结果分别是a, b, d, e, c, f, g, h和d, e, b, a, f, c, h, g, 求其后序遍历的结果

Answer 1

LRD:edbfhgca

设L、D、R分别表示遍历左子树、访问根结点和遍历右子树， 则对一棵二叉树的遍历有三种情况：DLR（称为先根次序遍历），LDR（称为中根次序遍历），LRD （称为后根次序遍历）。

由题意得：DLR：a, b, d, e, c, f, g, h

                 LDR：d, e, b, a, f, c, h, g

由先序遍历则可知道a为此二叉树的根节点，再通过中序遍历可知d, e, b,为左子树，f, c, h, g为右子树，接下来在分别把左子树和右子树当成独立的二叉树重复上面的方法可以很快得出左子树中b为根节点，d,e为左子树的左子树

右子树中c为根节点，f为右子树的左子树，g,h为右子树的右子树

左子树的左子树d为根节点，e为左子树的左子树右子树

右子树的右子树g为根节点，h为右子树的右子树左子树

所以：LRD:edbfhgca

Answer 2

先序就是 根左右
中序就是 左根右
所以先序的第一个a一定为根节点，则根据a将 中序的分为左右两部分 deb fchg
则先序也分为两部分 bde cfgh 则b是左子树的根节点 c是右节点的根 再遵循上面的步骤就可以画出树了。

后序 是 左右根
最后结果为
edbfhgca

追问

再接下去 b既然是根节点，那为什么de都是右子树。。

追答

是左子树啊？？怎么是右子树呢？？？

追问

噢。。左子树，那都是左子树怎么画

追答

再继续按这个步骤拆吧
de是左子树，先序中也是de，说明d是de这个左子树的根，而中序是de那说明e是d的右子节点

Answer 3

a
b c
d f g
e h
后续就是edbfhgca