解答:C。由前序和后序遍历序列可知...
解答:C。由前序和后序遍历序列可知3为根结点,故(1,2)为左子树,(4)为右子树,
C不可能。或画图即可得出结果。
方法一:构造
利用前序遍历序列和后序遍历序列构造所有可能的二叉树。
前序遍历是“根左右”遍历,后序遍历是“左右根”遍历。
第一轮递归:从前序遍历序列中取出第一个元素作为二叉树的根结点,从后序遍历序列中取出最后一个元素作为二叉树的根结点,这两个元素一定相同,否则无法构造二叉树,本题均为1。
第二轮递归:从前序遍历序列未处理的子串中取出第一个元素作为二叉树的左子树的根结点,从后序遍历序列未处理的子串中取出最后一个元素作为二叉树的右子树的根结点,这两个元素不一定相同。如果相同,说明有一个子树为空,本题均为2,也就是根结点只有一个孩子结点2,2可以随机分配在左子树或者右子树。
第三轮递归:从前序遍历序列未处理的子串中取出第一个元素作为二叉树的左子树的根结点,从后序遍历序列未处理的子串中取出最后一个元素作为二叉树的右子树的根结点,这两个元素不一定相同。如果相同,说明有一个子树为空,本题均为3,也就是根结点只有一个孩子结点3,3可以随机分配在左子树或者右子树。
第四轮递归:从前序遍历序列未处理的子串中取出第一个元素作为二叉树的左子树的根结点,从后序遍历序列未处理的子串中取出最后一个元素作为二叉树的右子树的根结点,这两个元素不一定相同。如果相同,说明有一个子树为空,本题均为4,也就是根结点只有一个孩子结点4,4可以随机分配在左子树或者右子树。
结点2、3和4均可能在其父结点的左子树或者右子树,根据乘法原理,总共有 2×2×2=8 种可能。
画出所以
对比选项,中序遍历序列不可能为3, 2, 4, 1。
本题选C。
方法二:利用选项构造
方法一是利用前序遍历序列和后序遍历序列构造二叉树。
我们知道前序遍历序列和中序遍历序列可以唯一确定一棵二叉树,我们可以利用题目的前序遍历序列和选项的中序遍历序列构造二叉树,最后检查该二叉树的后序遍历序列是否和题目的后序遍历序列一致。
检查得,用题目的前序遍历序列和C选项的中序遍历序列构造出的二叉树的后序遍历序列和题目的后序遍历序列不一致。
本题选C。
登录后提交答案