求证：二叉树高度的下界为lgn 技术问题求助

首先咱们先统一几个关键定义，避免歧义：

• 二叉树的高度h：这里指从根节点到最远叶子节点的路径上包含的节点层数（比如根是第1层，叶子节点在第h层，那h就是树的高度）。
• n：二叉树的总节点数。
• log₂n：以2为底n的对数，也就是题目里的lgn。

核心思路：先推导高度为h的二叉树最大节点数，再反推n个节点的二叉树高度下界 #

我们知道满二叉树是同高度下节点数最多的二叉树——每一层的节点数都是上一层的2倍：

• 第1层（根）：1个节点 = 2⁰
• 第2层：2个节点 = 2¹
• 第3层：4个节点 = 2²
• ...
• 第h层：2^(h-1)个节点

对高度为h的满二叉树总节点数做等比数列求和：

总节点数S = 2⁰ + 2¹ + 2² + ... + 2^(h-1) = 2ʰ - 1

这意味着：任何高度为h的二叉树，总节点数n ≤ 2ʰ - 1（非满二叉树的节点数肯定比同高度的满二叉树少）。

接下来对这个不等式变形，解出h的范围：

1. 移项得：n + 1 ≤ 2ʰ
2. 两边取以2为底的对数：log₂(n+1) ≤ h
3. 由于log₂(n+1) > log₂n（n+1>n），可进一步推出：h ≥ log₂(n+1) > log₂n

这就说明，任意n个节点的二叉树，高度h至少要大于log₂n，也就是高度的下界是log₂n。

反证法验证逻辑 #

假设存在一棵n个节点的二叉树，其高度h < log₂n（按层数定义），那根据满二叉树的节点数上限，这棵树的节点数最多是2ʰ -1。因为h < log₂n，所以2ʰ < n → 2ʰ -1 < n-1 < n，这就意味着这棵树最多只能容纳n-1个节点，和我们假设的n个节点矛盾。因此不存在这样的树，所有n个节点的二叉树高度必然≥log₂n。

补充：高度定义为边数的情况 #

如果题目里的“高度”指根到叶子的路径边数（比如根节点高度为0，叶子高度为h），推导逻辑类似：高度为h的满二叉树节点数是2^(h+1)-1，变形后可得h ≥ log₂(n+1)-1。这个值依然是对数级别的，且当n≥2时，log₂(n+1)-1 ≥ log₂n -1，依然符合“高度下界为lgn”的结论。

内容的提问来源于stack exchange，提问作者mdo123