binary-tree - n个节点的二叉树的最大和最小叶子节点数分别是多少？

Question

据我了解，n节点二叉树的最小叶子节点数为1，最大叶子节点数为⌈n/2⌉。我的假设是否正确？

Answer 1

• 二叉树的叶节点数 >= 1 是非常正确的。

• 叶节点数 <= ⌈n/2⌉:

证明:

• 对于n=1，叶节点数=1
• 对于每个 <1 left branch & 1 right branch under the same leaf>你阻止一片叶子变成这样，并创建 2 个新叶子 (每 2 个节点 +1 个叶子)
• 对于每个 <left branch>或 <right branch>你在一片叶子下创建，你阻止了一片叶子，并创建了 1 个新叶子 (+0 个叶子每 1 个节点)

因此，最大叶节点数 <= 1 + ((n-1)//2) = ⌈n/2⌉