引言 (Introduction)
二叉树（Binary Tree）是计算机科学中最基本的分层数据结构之一。它不仅是红黑树、B 树等高级数据结构的基础，更是理解递归思想、分治法和图遍历的关键。在算法面试与实际工程中，掌握二叉树的遍历模式与基本属性计算，是解决一切复杂树形问题的先决条件。
本文是本系列第一篇，系统探讨二叉树的深度优先遍历（DFS）、广度优先遍历（BFS）及核心结构属性算法。
首先，我们统一定义二叉树节点的标准数据结构（Python 类型提示规范）：
from typing import Optional, List
class TreeNode:
"""二叉树节点定义"""
def __init__(self, val: int = 0, left: 'Optional[TreeNode]' = None, right: 'Optional[TreeNode]' = None):
self.val = val
self.left = left
self.right = right
1. 深度优先遍历 (DFS)
深度优先遍历沿着一条分支走到最深处，然后再回溯。根据访问根节点的时机不同，分为前序、中序和后序遍历。
1.1 递归实现 (Recursive Approach)
递归实现的逻辑极其直观，它完美契合了二叉树的天然递归定义：一棵二叉树要么为空，要么由根节点、左子树和右子树构成。
def preorder_traversal(root: Optional[TreeNode]) -> List[int]:
"""前序遍历：根 -> 左 -> 右"""
res: List[int] = []
def dfs(node: Optional[TreeNode]) -> None:
if not node:
return
res.append(node.val) # 1. 访问根节点
dfs(node.left) # 2. 遍历左子树
dfs(node.right) # 3. 遍历右子树
dfs(root)
return res
def inorder_traversal(root: Optional[TreeNode]) -> List[int]:
"""中序遍历：左 -> 根 -> 右"""
res: List[int] = []
def dfs(node: Optional[TreeNode]) -> None:
if not node:
return
dfs(node.left) # 1. 遍历左子树
res.append(node.val) # 2. 访问根节点
dfs(node.right) # 3. 遍历右子树
dfs(root)
return res
复杂度分析：
- 时间复杂度：$O(N)$，其中 $N$ 为节点总数。每个节点恰好被访问一次。
- 空间复杂度：$O(H)$，其中 $H$ 为树的高度。空间消耗主要在于递归调用栈的深度。在最坏情况（退化为链表）下为 $O(N)$，在最优情况（完全二叉树）下为 $O(\log N)$。
1.2 迭代实现 (Iterative Approach)
递归虽然简洁，但在深度过大时可能会导致栈溢出（Stack Overflow）。我们可以使用显式的栈（Stack）来模拟系统调用栈，实现迭代遍历。这里以最常考的中序遍历为例：
def inorder_iterative(root: Optional[TreeNode]) -> List[int]:
"""迭代实现中序遍历"""
res: List[int] = []
stack: List[TreeNode] = []
curr = root
while curr or stack:
# 一路向左，将左侧路径上的所有节点压入栈中
while curr:
stack.append(curr)
curr = curr.left
# 此时左边已走到尽头，弹出节点，访问它，并转向它的右子树
curr = stack.pop()
res.append(curr.val)
curr = curr.right
return res
2. 广度优先遍历 (BFS)
广度优先遍历（或称层序遍历）按照树的层次，从上到下、从左到右逐层访问节点。常用于求解最短路径或处理具有层级关系的逻辑。
2.1 层序遍历实现
BFS 必须借助**队列（Queue）**的先进先出（FIFO）特性来实现。为了区分每一层的数据，我们可以在内部加一个循环，遍历当前队列中的所有元素（即当前层的所有节点）。
from collections import deque
def level_order(root: Optional[TreeNode]) -> List[List[int]]:
"""层序遍历二叉树"""
if not root:
return []
res: List[List[int]] = []
queue = deque([root])
while queue:
level_size = len(queue)
current_level: List[int] = []
# 遍历当前层的所有节点
for _ in range(level_size):
node = queue.popleft()
current_level.append(node.val)
# 将下一层的子节点加入队列
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(current_level)
return res
复杂度分析：
- 时间复杂度：$O(N)$，每个节点进队和出队各一次。
- 空间复杂度：$O(N)$。在最坏情况下（例如完全二叉树的最底层），队列中可能同时存放近似 $N/2$ 个节点。
3. 结构属性计算
基于上述的遍历思想，我们可以衍生出大量度量二叉树形态的算法。
3.1 二叉树的最大深度
一棵二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。 我们可以采用自底向上的后序遍历思维：一棵树的最大深度等于其左子树深度和右子树深度的最大值，再加上 $1$（根节点自身）。
def max_depth(root: Optional[TreeNode]) -> int:
"""计算二叉树的最大深度"""
if not root:
return 0
# 获取左右子树的深度
left_depth = max_depth(root.left)
right_depth = max_depth(root.right)
# 取最大值并 +1
return max(left_depth, right_depth) + 1
3.2 翻转二叉树 (Invert Binary Tree)
题目描述：给定一棵二叉树的根节点，翻转这棵二叉树，并返回其根节点（LeetCode 226）。 核心逻辑：我们需要将每个节点的左右孩子进行交换。这同样是一个后序遍历的过程：先把左子树内部翻转好，再把右子树内部翻转好，最后把当前节点的左右指针调换。
def invert_tree(root: Optional[TreeNode]) -> Optional[TreeNode]:
"""翻转一棵二叉树"""
if not root:
return None
# 先递归翻转左右子树
left_inverted = invert_tree(root.left)
right_inverted = invert_tree(root.right)
# 将当前节点的左右孩子进行对换
root.left = right_inverted
root.right = left_inverted
return root
结论 (Conclusion)
无论是 DFS 的递归与迭代，还是 BFS 的队列模拟，这些基础遍历手段构成了树形算法的骨架。深入理解每一层递归调用时系统栈的状态，是学好这部分内容的关键。下一篇我们将探讨具有严格排序约束的二叉搜索树（BST）及其相关的拓扑路径逻辑问题。