Question

数据结构知道先序遍历和中序遍历怎么求后续遍历？

Answer 1

找到根节点(通过后序),然后将中序序列分成两段，左右子树，然后递归进行，分的时候可以利用求中序的左右子树的结点个数来确定后序序列的每段节点个数.

例如：中  BDACE   后  DBECA

1.由后序遍历的知道最后一个节点一定是根节点,该例中为A

2.中序中对应的根就是A,推得A为根BD为左子树CE为右子树

3.左子树2个结点右子树也为2个,因为后序遍历是先左再右因此将后序分为两段左DB,右EC

4.由此确定左子树的根为B,右子树根为C

5.在回到中序中左子树部分 BD (B为根)其右子树为D  左子树部分 根为C右子树为E

得前序为 ABCDE