已知二叉树的后序遍历序列和中序遍历序列,怎样求其前序遍历序列!

如题所述

首先理解概念:
前序遍历:访问根结点的操作发生在遍历其左右子树之前。
中序遍历:访问根结点的操作发生在遍历其左右子树之中(间)。
后序遍历:访问根结点的操作发生在遍历其左右子树之后。
eg:后序遍历为DBCEFGHA,中序遍历为EDCBAHFG,求前序遍历(网上例子)
解:首先看后序遍历DBCEFGHA,A为总根节点
然后寻找中序遍历EDCBAHFG中A位置,则EDCB在A的左枝,HFG在A的右枝;
重复前两步,从后序遍历最后一位找,在中序遍历寻找对应点,得出左右分枝...
最后得到AECDBHGF,再自己验证即可...
温馨提示:答案为网友推荐,仅供参考