求二叉树的叶子结点数

Question

输入一个字符串,并建成一棵二叉树,满足左子树的字符都要小于根结点的字符,右子树的字符都要大于根结点的字符，求该二叉树的叶子结点数

Answer 1

这个问题是给定N个节点构造BST，求叶子节点的数目。但是题目缺少条件，只能求得一个范围。

首先证明这个问题有多解的可能，举一个简单的反例即可说明

1：假设S=abc，叶子节点数为1

2：假设S=bac，叶子节点数为2

-----

既然解不唯一，则求出范围：

1：最差情况：如果输入的是一个顺序序列，叶子节点数=1；

2：最好情况：如果形成了平衡二叉树，其最理想的情况，恰巧是完全二叉树，则叶子节点数M=

h=[log2N]+1

叶子节点存在于最底层和倒数第二层，1~h-1层是全满的，共有节点2^(h-1)-1个，所以

h层有有叶子节点N-2^(h-1)+1个；

h-1层的叶子节点数和h层的节点数有关，h-1层的叶子节点数为：

2^(h-2)-[N-2^(h-1)+1+1]/2//+1是因为这里要上取整

整理可得，共有叶子节点数：

N-2^(h-1)+1+2^(h-2)-[N-2^(h-1)+1+1]

//进一步整理的结果见图片，baidu不能输入公式真是太别扭了。。