返回主页
已有30条笔记
[数据结构 P1507] 先序序列为 a,b,c,d 的不同二叉树的个数是（）。 A．13 B．14 C．15 D．16
未通过
先序序列为 a,b,c,d 的不同二叉树的个数是（）。
A．13 B．14 C．15 D．16
上面问题的答案是：
加入错题本
个人笔记
方法一：枚举
先序序列为满足...
用户登录可进行刷题及查看答案
方法一：枚举
先序序列为满足二叉树递归遍历顺序为“根左右”的输出序列。
其实只要枚举一半就行，本人枚举了左子树结点数大于右子树结点数的所有情况，另一半对称，总计 7×2=14 。
但注意，如果结点个数为奇数个，需要考虑左子树结点数等于右子树结点数的情况。
本题选B。
方法二：计算
可以发现，暴力枚举需要非常小心，稍有不慎就会遗漏。如果先序序列为入栈顺序，中序序列为出栈顺序，由先序序列和中序序列可以唯一的确定一棵二叉树，出栈序列为 �=4 的卡特兰数： 
。
本题选B。
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后提交答案