二叉树最大最小高度定义疑问及32节点树最大高度求解

一、两种高度定义的核心区别 #

二叉树高度的数值差异，本质是计数基准不同，两种定义都被行业认可，没有对错之分，仅需对应具体资料的约定：

• 节点计数法：高度统计的是从根到最远叶子的路径上的节点总数
  • 单节点树高度为1；链状二叉树（每个节点仅一个子节点）的最大高度为N（N为节点总数）。
  • 最小高度正确表达式应为 ⌊log₂N⌋ + 1（或等价的 ⌈log₂(N+1)⌉），你教材中的⌈log₂N+1⌉大概率是输入/排版误差——按这个公式计算会得到偏大的错误结果，比如N=3时会算出3，但实际3节点二叉树的最小高度是2。
• 边计数法：高度统计的是从根到最远叶子的路径上的边总数
  • 单节点树高度为0；链状二叉树的最大高度为N-1。
  • 最小高度公式：⌈log₂(N+1)⌉ - 1，和你看到的外部资料一致。

二、32个节点的二叉树最大高度 #

• 若用节点计数法：最大高度为32（树呈纯链状，每个节点只连一个子节点，根到最后一个叶子的路径包含全部32个节点）。
• 若用边计数法：最大高度为31（链状树的边数等于节点数减1，即32-1=31）。

三、仅给定节点数时的高度计算逻辑 #

最大高度 #

无论哪种定义，最大高度都对应极端链状结构：

• 节点计数法：H(max) = N
• 边计数法：H(max) = N - 1

最小高度 #

最小高度对应完全二叉树结构（每一层尽可能填满，仅最后一层从左到右排列）：

• 节点计数法：找到最小的h，使得满二叉树的节点数2^h - 1大于等于N，即 h = ⌈log₂(N+1)⌉；也可以用⌊log₂N⌋ + 1计算，结果一致。
  示例：N=32时，⌈log₂(32+1)⌉=6，所以最小高度为6。
• 边计数法：找到最小的h，使得满二叉树的节点数2^(h+1)-1大于等于N，即 h = ⌈log₂(N+1)⌉ - 1。
  示例：N=32时，⌈log₂33⌉-1=5，所以最小高度为5。

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