🌳 二叉树 — 递归的完美舞台

📖 二叉树的核心概念

二叉树（Binary Tree）是每个节点最多有两个子节点的树结构。二叉树是递归定义的——一棵二叉树要么为空，要么由根节点、左子树和右子树组成。这个递归定义使得二叉树的几乎所有问题都可以用递归优雅地解决。

1. 二叉树递归思维框架

2. LeetCode 二叉树节点定义

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

🎯 题目一：二叉树的最大深度 (LC 104)

题目描述：给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

思路分析

代码实现

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

复杂度分析

时间复杂度：O(n) — 访问每个节点一次

空间复杂度：O(h) — 递归栈深度

变体练习

• LC 111 二叉树的最小深度
• LC 559 N 叉树的最大深度

🎯 题目二：翻转二叉树 (LC 226)

题目描述：给你一棵二叉树的根节点 root，翻转这棵二叉树，并返回其根节点。

思路分析

代码实现

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        root.left, root.right = root.right, root.left
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root

复杂度分析

时间复杂度：O(n)

空间复杂度：O(h)

变体练习

• LC 101 对称二叉树（判断是否镜像对称）
• LC 100 相同的树

🎯 题目三：二叉树的层序遍历 (LC 102)

题目描述：给你二叉树的根节点 root，返回其节点值的层序遍历（即逐层地，从左到右访问所有节点）。

思路分析

代码实现

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        from collections import deque
        if not root:
            return []
        result = []
        queue = deque([root])
        while queue:
            level = []
            for _ in range(len(queue)):
                node = queue.popleft()
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            result.append(level)
        return result

复杂度分析

时间复杂度：O(n)

空间复杂度：O(w) — w 为树的最大宽度

变体练习

• LC 103 二叉树的锯齿形层序遍历（之字形）
• LC 107 二叉树的层序遍历 II（自底向上）
• LC 637 二叉树的层平均值

📝 课后练习

1. LC 101 对称二叉树（递归判断左右镜像）
2. LC 111 二叉树的最小深度
3. LC 110 平衡二叉树（后序递归判断）
4. LC 257 二叉树的所有路径（前序遍历+回溯）
5. LC 103 二叉树的锯齿形层序遍历

🔑 本课要点回顾

• 二叉树递归三要素：返回值、递归基、利用左右子树结果
• 自顶向下（前序）：先处理当前，再递归子树
• 自底向上（后序）：先递归子树，再利用结果
• 最大深度：max(左, 右) + 1，后序递归
• 翻转：交换左右子树，前序或后序都可以
• 层序遍历：BFS + 记录每层大小，区分层级

📚 扩展阅读

• 《算法导论》第12章 二叉搜索树
• 二叉树专题：LeetCode 二叉树标签
• 可视化：visualgo.net/en/bst

🔬 二叉树的序列化与反序列化

二叉树的序列化是将树转化为字符串，反序列化是还原。这是面试中的经典设计题，也是对递归思维的深度考验。

代码实现

class Codec:
    def serialize(self, root):
        if not root:
            return 'null'
        return f'{root.val},{self.serialize(root.left)},{self.serialize(root.right)}'
    
    def deserialize(self, data):
        vals = iter(data.split(','))
        def build():
            val = next(vals)
            if val == 'null':
                return None
            node = TreeNode(int(val))
            node.left = build()
            node.right = build()
            return node
        return build()