5.1 二叉树的结构与递归
前置：递归入门，约 25 分钟。本节先读懂节点、边、深度与高度，再从递归契约写出计数、求高和普通查值。
一个节点怎样连成一棵树
节点保存一个值和 left、right 两条孩子链接。链接为空，表示这个位置没有孩子；只有左孩子和只有右孩子是两种不同的形状。
1 depth 0
/ \
2 3 depth 1
/ \ \
4 5 6 depth 2这是一棵二叉树，因为每个节点最多有两个孩子。图中的值没有排序含义：2 在 1 左边，不代表 2 必须小于 1。二叉搜索树会额外约束左右子树的 key 大小，本页先讨论不带这种顺序的普通二叉树。
一棵非空树有一个根。除了根以外，每个节点恰好有一个父节点，因此包含 n 个节点的非空树有 n - 1 条父子边。节点不能沿孩子链接重新回到祖先，否则结构会形成环，不再是树。
术语与边界
| 术语 | 本页约定 |
|---|---|
| 根（root） | 没有父节点的起点；样例中是 1 |
| 叶（leaf） | 左右孩子都为空；样例中是 4、5、6 |
| 内部节点 | 至少有一个孩子的节点；根也可以是内部节点 |
| 边（edge） | 一条父子链接 |
| 路径（path） | 沿边连接的一串节点 |
| 祖先/后代 | 位于某节点上方/下方的节点 |
| 子树（subtree） | 一个节点连同它的全部后代 |
| 深度（depth） | 从根到该节点的边数；根深度为 0 |
| 高度（height） | 从该节点到最远叶的边数；叶高度为 0 |
“内部节点既不是根也不是叶”不是通用定义。根只要有孩子，也是内部节点。
高度有两套常见计数法：按边数或按节点数。本页按边数计算，因此叶高为 0；为了让递归式 height(node) = 1 + max(...) 对叶成立，代码把空树高度约定为 -1。换教材时先核对约定，算法本身没有变化。
结构递归
二叉树的定义天然递归：一棵树要么为空，要么由一个根、左子树和右子树组成。写递归函数时只需回答三件事：
- 空树返回什么。
- 函数对左、右子树分别承诺什么。
- 当前节点怎样合并两个子结果。
下面的程序构造样例树，并实现节点计数、按边求高和普通查值。这里的 contains_value 不利用大小关系，所以最坏要访问全部节点。
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def build_sample_tree():
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)
return root
def count_nodes(root):
if root is None:
return 0
return 1 + count_nodes(root.left) + count_nodes(root.right)
def tree_height_edges(root):
"""按边数计算高度：空树 -1，叶节点 0。"""
if root is None:
return -1
return 1 + max(
tree_height_edges(root.left),
tree_height_edges(root.right),
)
def contains_value(root, target):
if root is None:
return False
if root.value == target:
return True
return (
contains_value(root.left, target)
or contains_value(root.right, target)
)
sample = build_sample_tree()
assert count_nodes(None) == 0
assert count_nodes(sample) == 6
assert tree_height_edges(None) == -1
assert tree_height_edges(TreeNode(9)) == 0
assert tree_height_edges(sample) == 2
assert contains_value(sample, 5)
assert not contains_value(sample, 99)拆开 count_nodes
空树有 0 个节点。非空树的节点数等于：
当前根的 1 个节点 + 左子树节点数 + 右子树节点数你不需要在脑中展开全部调用。把递归函数当作对子树的合同：“给我一棵子树，我返回其中的节点数。”当前层只负责加 1。
拆开 tree_height_edges
空树返回 -1，叶的两个空孩子都返回 -1，所以叶高是 1 + max(-1, -1) = 0。对任意内部节点，较高子树决定最远叶的位置。
拆开 contains_value
普通二叉树没有顺序可供剪枝。当前节点不匹配时，左右子树都可能藏着目标；短路运算只会在左侧已找到时省去右侧搜索。最坏时间仍为 O(n)。
形状比名字多
二叉树可以有多种形状：
- 严格二叉树（full/proper）的每个内部节点都有两个孩子。
- 完美二叉树（perfect）的内部节点都有两个孩子，叶还位于同一深度。
- 完全二叉树除最后一层外都填满，最后一层从左向右连续填充。
- 链状树的每个节点最多只有一个孩子。
- 平衡的具体定义取决于数据结构；AVL 与红黑树使用不同约束。
本页按 NIST 的 full 定义区分严格树与完美树。不同资料会把“满二叉树”用于不同形状，遇到这个名称要先看它是否要求叶深相同。完全二叉树则按最后一层靠左填充定义。
这些形状影响高度和存储。n 个节点的链状树高为 n - 1；完美树满足 n = 2^(h+1) - 1，所以 h = log₂(n+1) - 1。
递归的时间与空间
count_nodes、tree_height_edges 和最坏情况下的 contains_value 都访问每个节点一次，按节点访问和固定成本比较计，时间为 Θ(n)。
对非空树，调用栈保存根到当前节点的一条路径，因此辅助空间是 O(h + 1)；加 1 计入高度为 0 的叶节点。空树调用仍需常数空间：
- 高度接近
log n时，栈也接近O(log n)。 - 链状树的栈深为
O(n)。
Python 的递归上限由解释器配置和平台决定。可以用 sys.getrecursionlimit() 查看当前值，但不应把它当作安全容量，也不要仅靠调高上限处理不可信深树。迭代遍历把隐式调用栈换成显式容器，仍可能需要 O(h + 1) 空间，却避免依赖递归调用深度。
常见错误
把空链接当作节点
访问 root.left 前没有处理 root is None，会触发属性错误。递归函数通常先写空树基线。
混用高度定义
代码按节点数计高，公式却按边数解释，容易出现一位偏差。把“空树与叶分别多高”写在函数注释里。
看到左右孩子就假设有序
左右是位置，不是大小。普通二叉树查值需要检查两侧；BST 才能只走一边。
用共享默认列表收集结果
Python 的 def walk(node, result=[]) 会在多次调用间复用同一个列表。可把默认参数设为 None，进入函数后再检查并新建列表，或由每次外层调用创建结果并传给辅助函数。
输入可能不是树
若对象图包含环或多个父节点，递归可能重复访问或无限循环。处理外部构造的数据时，可用对象身份集合检测重复节点。
结构操作速查
| 任务 | 常用模式 | 时间 | 辅助空间 |
|---|---|---|---|
| 节点计数 | 后序合并 | O(n) | O(h + 1) |
| 求高度 | 后序取最大值 | O(n) | O(h + 1) |
| 判断普通树是否含值 | DFS/BFS | O(n) | DFS O(h + 1)，BFS O(w) |
| 复制树 | 前序创建节点，再复制子树 | O(n) | O(h + 1) |
| 比较两棵树 | 同步递归左右子树 | O(n) | O(h + 1) |
h 是按边计的高度，w 是最大层宽；空树操作按常数计。复制树一行只统计新树以外的辅助空间，新节点本身另占 Θ(n)，深复制负载的成本也需另计。比较两棵树时，n、h 可取两棵输入树的较大节点数与高度，比较可能提前结束。若输入允许共享节点或环，就应按对象图另行分析。
动手拆解结构递归
- 给样例树每个节点标出深度与高度。
- 把节点 6 移到节点 5 的左侧，重新计算根高度。
- 写
sum_values(root)，先给出空树返回值和合并公式。 - 写
same_shape(a, b)，只比较结构，不比较值。 - 用迭代 DFS 重写
contains_value，比较其显式栈与递归调用栈。
读懂树形之后
二叉树只限制“每个节点最多有两个孩子”，并不自动附带排序或平衡。写结构递归时，先固定空树返回值，再相信左右子树会完成同一份契约，当前层只负责合并。时间通常取决于访问的节点数，调用栈则取决于树高；一条长链足以把 O(h + 1) 推到 O(n)。
现在你已经能看清树的形状。下一节给 key 加上严格的左右顺序，进入 二叉搜索树的增删查；随后再比较 递归、显式栈与队列实现的树遍历。