数据结构与算法 / 系统课时
二叉树的高度与节点统计
二叉树的高度与节点统计
树高、节点总数和叶子数量都依赖子树结果,适合用后序递归一次完成。本课统一高度定义,设计一个返回多个统计值的函数,避免为每个指标重复遍历整棵树。
学习目标
- 使用递归计算树高、节点数和叶子数
- 理解后序汇总与返回值设计
- 分析一次遍历和重复遍历的差异
先统一高度定义
本课按“层数”定义树高:空树高度为 0,单节点树高度为 1。非空树高度等于左右子树最大高度加 1。若需要按边数表示非空树高度,只需将本课结果减 1。
节点总数等于左子树节点数、右子树节点数与当前节点之和。叶子节点没有左右孩子,应直接返回 1;非叶子节点的叶子数才等于左右子树叶子数之和。

为什么使用后序递归
当前节点的高度和统计值必须等待左右子树计算完成,因此处理顺序是“左子树、右子树、当前节点”。一次递归可以同时返回多个结果,比调用三个独立遍历函数更节省重复工作,也比修改全局变量更容易测试和复用。
主示例:一次遍历返回三个指标
python
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def analyze(node):
if node is None:
# 空树按层数计高为 0,也没有节点和叶子
return 0, 0, 0
left_height, left_nodes, left_leaves = analyze(node.left)
right_height, right_nodes, right_leaves = analyze(node.right)
height = max(left_height, right_height) + 1
nodes = left_nodes + right_nodes + 1
# 叶子必须单独返回 1,否则左右空子树之和仍是 0
if node.left is None and node.right is None:
leaves = 1
else:
leaves = left_leaves + right_leaves
return height, nodes, leaves
root = Node(
"A",
Node("B", Node("D"), Node("E")),
Node("C", None, Node("F")),
)
height, nodes, leaves = analyze(root)
print("树高:", height)
print("节点数:", nodes)
print("叶子数:", leaves)预期输出
text
树高: 3
节点数: 6
叶子数: 3复杂度与扩展
每个节点只汇总一次,时间复杂度为 ,递归栈空间为 。如果在每个节点上重新调用高度函数来判断平衡,最坏情况下会重复扫描子树并退化到 ;更好的做法是在同一次后序遍历中继续返回“是否平衡”等信息。
高度定义是最常见的偏差来源。测试时至少覆盖空树、单节点树、只有左链或右链的退化树,以及左右高度不同的普通树。
按自己的节奏,确认真正理解。