题36

题36

题目

Q:【2012 统考真题】若一棵二叉树的前序遍历序列为 ,后序遍历序列为 ,则根结点的孩子结点 ( ).
A. 只有
B. 有
C. 有
D. 无法确定

分析

A:前序，根左右
后续，左右根
如果前序遍历和后续遍历的第二个元素是一样的，那么我们可以得到一个结论，但是这个结论好像是错的，有的不理解了现在

Transclude of 前序和后序遍历-aw#分析

解

A
前序序列和后序序列不能唯一确定一棵二叉树, 但可以确定二叉树中结点的祖先关系:
当两个结点的前序序列为 与后序序列为 时,则 为 的祖先。
考虑前序序列 、后序序列 ,可知 为根结点, 为 的孩子结点;
此外,由 的孩子结点的前序序列 、后序序列 ，可知 是 的祖先,所以根结点的孩子结点只有 。
排除法: 显然 为根结点,且确定 为 的孩子结点,排除 。各种遍历算法中左右子树的遍历次序是固定的,若 也为 的孩子结点,则在前序序列和后序序列中 的相对次序应是不变的,所以排除 ,同理排除 。
特殊法: 前序序列和后序序列对应多棵不同的二叉树树形, 我们只需画出满足该条件的任意一棵二叉树即可, 任意一棵二叉树必定满足正确选项的要求。
显然选择 A, 最终得到的二叉树满足题设中前序序列和后序序列的要求。