Question

已知某森林的先序遍历次序为ADEFGHBICJKLMN,中序遍历为DFGHEAIBJLMNKC,画出该森林。谢谢

Answer 1

用递归思想来做：
首先先根遍历的第一个节点“A”必定为当前的根节点，然后到中根遍历中找到该节点，“A”前面的“CBED”必定属于左子树，“A”后面的“GHFJI”必定属于右子树。
由于左子树的中根遍历长度为4，故到先根遍历中截取长度为4的遍历，即为左子树的先根遍历，这样就同时找到了左子树的这两种遍历，又可以如法炮制，构造左子树。
对于右子树，同样可以根据他的中根遍历长度截取其先根遍历。
这样就是，构造二叉树的全过程。