Question

先序遍历序列和中序遍历序列相同的二叉树为()。

A.根结点无左子树的二叉树
B.根结点无右子树的二叉树
C.只有根结点的二叉树或非子结点只有左子树的二叉树
D.只有根结点的二叉树或非叶子结点只有右子树的二叉树

Answer 1

【答案】：D
先序遍历的次序为根一左一右，而中序遍历的次序为左一根一右，树中肯定有根结点，要使先序遍历序列和中序遍历序列相同，两种遍历次序可以相同的次序为根一右。所以满足条件的树为只有根结点的二叉树或非叶子结点只有右子树的二叉树。