Question

数据结构二叉树，已知中序遍历、后序遍历，如何求先序遍历？

Answer 1

Preorder遍历:访问根节点的操作发生在遍历左和右子树之前。

中间顺序遍历:访问根节点的操作发生在左边和右边的子树中。

顺序遍历:访问根节点的操作发生在遍历左边和右边的子树之后。

下面的序列遍历了DBCEFGHA，序列遍历是EDCBAHFG，以及preorder遍历(在线示例)

解决方案:首先，看到后序遍历DBCEFGHA, A是总根节点。

然后发现中间顺序遍历A在EDCBAHFG中的位置，然后在A的左分支上的EDCB，在A的右分支上的HFG;

重复前两个步骤，最后一个从后序遍历，在中间顺序遍历中搜索相应的点，以及左和右分支…

最后，AECDBHGF可以自行验证。