2.【2019年第14题】假设一棵二叉树的后序遍历序列为DGJHEBIFCA,其中序遍历序列为DBGEHJACIF,则其前序遍历序列为( )。
【解析】先通过后序遍历确定根节点,再根据中序遍历确定左子树和右子树,按照这样的方法画出整棵二叉树,根据前序遍历规则即可求出答案。由后序遍历序列DGJHEBIFCA可知,A为整棵树的根节点,推出中序遍历序列DBGEHJACIF里,A左边的DBGEHJ都是A的左子树节点,对应的后序遍历序列为DGJHEB,A右边的CIF都是A的右子树节点,对应的后序遍历序列为IFC;接下来用同样的方法能确定B是A的左子树根节点,C是A的右子树根节点……最后画出如图所示的一棵树。
【答案】B