单选题
适中
#16703
某二叉树共有10个结点,记为A~J,已知它的先序遍历序列为:<strong>AB D H I E C F J G</strong>,中序遍历序列为:<stron…
某二叉树共有10个结点,记为A~J,已知它的先序遍历序列为:<strong>AB D H I E C F J G</strong>,中序遍历序列为:<strong>H DI B E A FJ C G</strong>,则该二叉树的后序遍历序列是()。
答案与解析
正确答案:A
解析
根据先序遍历序列确定根节点,结合中序遍历序列划分左右子树。先序序列首元素为当前子树根节点,在中序序列中找到该根节点位置,其左侧为左子树结点,右侧为右子树结点。递归应用此过程,重建各子树结构。每层递归均按先序定位根、中序分左右的方式推进,直至所有结点位置确定。后序遍历顺序为左子树、右子树、根节点,依据重建的树结构进行访问即可得到后序序列。