数据结构与算法 / 系统课时

二叉树的高度与节点统计

二叉树的高度与节点统计

树高、节点总数和叶子数量都依赖子树结果,适合用后序递归一次完成。本课统一高度定义,设计一个返回多个统计值的函数,避免为每个指标重复遍历整棵树。

学习目标

  • 使用递归计算树高、节点数和叶子数
  • 理解后序汇总与返回值设计
  • 分析一次遍历和重复遍历的差异

先统一高度定义

本课按“层数”定义树高:空树高度为 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

复杂度与扩展

每个节点只汇总一次,时间复杂度为 O(n)O(n),递归栈空间为 O(h)O(h)。如果在每个节点上重新调用高度函数来判断平衡,最坏情况下会重复扫描子树并退化到 O(n2)O(n^2);更好的做法是在同一次后序遍历中继续返回“是否平衡”等信息。

高度定义是最常见的偏差来源。测试时至少覆盖空树、单节点树、只有左链或右链的退化树,以及左右高度不同的普通树。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

二叉树的高度与节点统计

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通