Question

若一棵二叉树高度为H，其上只有度为0和度为2的结点，则此二叉树中包含结点数至少为多少。

求高手帮忙，希望有详细解释，非常感谢！

Answer 1

此二叉树中包含的结点数至少为 2*H-1

考虑按如下规则构造一棵高度为H的二叉树，可使得其节点数最少：

1) 构造一个根结点

2) 为根结点构造2个儿子结点

3) 如果树的高度已经达到H，则结束；否则以上一步的根结点的右儿子最为新的根结点，重复步骤2.

图片展示了上述过程是如何构造这种二叉树的。