本文共 518 字,大约阅读时间需要 1 分钟。
两个字符串,其长度n均小于等于26。第一行为前序遍历,第二行为中序遍历。二叉树中的结点名称以大写字母表示:A,B,C....最多26个结点。
输入样例可能有多组,对于每组测试样例,输出一行,为后序遍历的字符串。
ABCBACFDXEAGXDEFAG
BCAXEDGAF
由于先序遍历的时候,首个字符即为根节点,可以利用根节点在中序遍历的序列中找到左右子树的先序,和中序字符串。然后用递归去还原整棵树。最后再写个后序遍历的方法,当然用递归也是最简单的。即可还原后序字符串。
有个细节就是System.out.print会一直把字符往后加,所以每次还原一棵树后,打印一个换行符,下一次输出就正常了。这一点反而找了很久。。。郁闷
转载地址:http://hfdii.baihongyu.com/