已知某二叉树的后序遍历序列是dabec,中序遍历序列是deabc,它的前序遍历序列是?

后序:左 右 根
中序:左 根 右
由定义可以知道:
1、后序遍历中最后一个就是树根节点,即C节点
2、在中序遍历中,根结点左边的是左儿子集,右边的是右儿子集,即deab是根节点C的左儿子集合
问题就会转化为:
求后序遍历是dabe,中序遍历是deab的子树,方法同上
因为中序遍历中,C节点右边没有节点了,所以C节点不包含右儿子,否则就会被分为2个子问题
以下是这道题的详细推理过程:
1、由dabec得出根结点为C,由中序遍历可知:{deab}c,二叉树如下

      C
     / \
{deab} {右儿子为空}

2、由dabe得出左儿子集合的根节点为e,由中序可知:{d}e{ab},二叉树更新后如下

    C
   / 
  e 
 / \
d  {ab}

3、由ab可知,e的右儿子集合的根节点为b,由中序可知{a}b,二叉树更新后如下

     C
    / 
   e 
  / \
 d   b
    /
   a

4、由上图可得,前序遍历为:cedba


问题出处:
https://www.zybang.com/question/9bb2cf55fbffcf82890fa4d1309775d0.html