二叉树是一种分层结构,其中每个节点最多有两个子节点,分别称为 left 和 right。它有一个根节点;没有子节点的节点称为叶节点。它是 BST、堆和表达式树的基础。
Structure
text
1 depth 0 (root)
/ \
2 3 depth 1
/ \
4 5 depth 2 (leaves: 4,5,3)
class Node:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def inorder(n): # left, node, right -> 4 2 5 1 3
if n:
inorder(n.left); print(n.val); inorder(n.right)
def preorder(n): # node, left, right -> 1 2 4 5 3
if n:
print(n.val); preorder(n.left); preorder(n.right)
def postorder(n): # left, right, node -> 4 5 2 3 1
if n:
postorder(n.left); postorder(n.right); print(n.val)
level-order(BFS)遍历使用队列,按深度逐层访问节点。
| 遍历方式 | 顺序 | 常见用途 |
|---|---|---|
| 中序遍历 | L, N, R | BST 的有序输出 |
| 前序遍历 | N, L, R | 复制/序列化树 |
| 后序遍历 | L, R, N | 删除树、计算表达式 |
| 层序遍历 | by depth | BFS、树上的最短路径 |
每种遍历都访问每个节点一次 → O(n) 时间复杂度,O(h) 栈空间(其中 h 是树的高度)。
二叉树自然地模拟分层数据(文件系统、解析树、决策树),并且是高效搜索和排序结构的基础。
掌握四种遍历方法至关重要——大多数树形结构的面试题都是其中一种遍历方式的变体。