单选题
适中
#24813
某二叉树共有 10 个结点,记为 A~J,已知它的先序遍历序列为: A B D H I E C F J G ,中序遍历序列为: H D I B E A F J…
某二叉树共有 10 个结点,记为 A~J,已知它的先序遍历序列为:A B D H I E C F J G,中序遍历序列为:H D I B E A F J C G,则该二叉树的后序遍历序列是( )。
答案与解析
正确答案:A
解析
根据先序遍历序列确定根节点,结合中序遍历序列划分左右子树。先序序列首元素为当前子树根节点,在中序序列中定位该节点,其左侧为左子树中序序列,右侧为右子树中序序列。通过左右子树结点数量反推先序序列中对应子树的范围。递归构建左右子树结构,直至所有子树均分解至空或单个结点。后序遍历顺序为左子树、右子树、根节点,依据重建的树结构按此顺序收集结点即可得到后序序列。