如何根据后序和中序建立二叉树。

Question

注意：是建立二叉树！前序建立解法一大片，哪位大神告诉我后序和中序的方式，最好能用代码实现，万分感激！

Answer 1

这个跟前序+中序建立二叉树的方法类似，重点在于理解遍历方式中各子树在序列中出现的顺序关系

根据后序和中序建立二叉树的一种递归解法如下：

1、得到有后序序列的最后一个节点，设为a，除去最后一个节点前边序列为 S0

2、在中序序列中查找a的位置，其左边序列为S1,右部序列为S2,即 S1 a S2

3、根据S1、S2的长度将S0划分为两个序列S01, S02

4、该序列对应的根节点为a，左子树为根据后序序列S01和中序序列S0得到的子树，右子树为根据后序序列S11和中序序列S1得到的子树