先序序列为 a,b,c,d 的不同二叉树的个数是()。
A.13 B.14 C.15 D.16
卡特兰数公式
方法一:枚举
先序序列为满足...
用户登录可进行刷题及查看答案
先序序列为满足二叉树递归遍历顺序为“根左右”的输出序列。
其实只要枚举一半就行,本人枚举了左子树结点数大于右子树结点数的所有情况,另一半对称,总计 7×2=14 。
但注意,如果结点个数为奇数个,需要考虑左子树结点数等于右子树结点数的情况。
本题选B。
方法二:计算
可以发现,暴力枚举需要非常小心,稍有不慎就会遗漏。如果先序序列为入栈顺序,中序序列为出栈顺序,由先序序列和中序序列可以唯一的确定一棵二叉树,出栈序列为 �=4 的卡特兰数: 。
登录后提交答案