二叉树是算法学习的"分水岭":数组、链表都是线性结构,顺着一条线走就行;二叉树第一次引入"分支"和"递归",很多人在这一步被劝退。别怕,这篇文章从节点定义开始,把四种遍历、重建二叉树、最大深度等高频题型一次讲透,代码全部可运行。

1. 节点与构建:把一棵树"画"进内存

二叉树是每个节点最多有两个孩子(left 和 right)的树结构。和链表一样,它也是用"节点 + 指针"表示的,只不过链表只有一个 next,二叉树有两个指针。下面的 build_tree 把层序数组(空位用 None 占住)还原成树,用的是 BFS 的思路:父节点出队时,按顺序给它挂上左右孩子。

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def build_tree(vals):
    """层序数组 -> 二叉树,None 表示空位"""
    if not vals or vals[0] is None:
        return None
    root = TreeNode(vals[0])
    q = deque([root])
    i = 1
    while i < len(vals):
        node = q.popleft()
        if vals[i] is not None:
            node.left = TreeNode(vals[i])
            q.append(node.left)
        i += 1
        if i < len(vals) and vals[i] is not None:
            node.right = TreeNode(vals[i])
            q.append(node.right)
        i += 1
    return root

# 树结构:
#       1
#      / \
#     2   3
#    / \   \
#   4   5   6
root = build_tree([1, 2, 3, 4, 5, None, 6])

这个构建函数是理解"层序"的好例子:队列里永远装着"还没分配孩子的节点",先到先分配,所以叫广度优先。后面做题时,我们可以直接用它快速造出测试树,省去手动一个个建节点的痛苦。

2. 递归遍历:前序、中序、后序

三种深度优先遍历的区别只在访问根节点的时机:前序"根左右"、中序"左根右"、后序"左右根"。用递归写,代码几乎一模一样——因为递归本身就是"把大问题拆成同样的小问题",遍历左子树和右子树就是两个同构的子问题。

def preorder(root):
    if root is None:
        return []
    return [root.val] + preorder(root.left) + preorder(root.right)

def inorder(root):
    if root is None:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

def postorder(root):
    if root is None:
        return []
    return postorder(root.left) + postorder(root.right) + [root.val]

root = build_tree([1, 2, 3, 4, 5, None, 6])
print(preorder(root))    # [1, 2, 4, 5, 3, 6]
print(inorder(root))     # [4, 2, 5, 1, 3, 6]
print(postorder(root))   # [4, 5, 2, 6, 3, 1]

记住一个实用结论:中序遍历一棵二叉搜索树,得到的是有序序列。所以"验证一棵树是不是二叉搜索树"最朴素的解法就是中序遍历后检查是否递增,这也是中序在面试里出现频率最高的原因。

3. 迭代遍历:用栈模拟递归

递归写起来爽,但深树会栈溢出,而且面试官常追问"不用递归怎么写"。迭代版的核心是显式地用栈模拟函数调用栈:一路向左把节点压栈,走到头就弹出并转向右子树。下面是中序遍历的迭代写法,前序后序也大同小异。

def inorder_iter(root):
    res = []
    stack = []
    cur = root
    while cur or stack:
        while cur:            # 一路向左,入栈
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()     # 弹出,访问
        res.append(cur.val)
        cur = cur.right       # 转向右子树
    return res

root = build_tree([1, 2, 3, 4, 5, None, 6])
print(inorder_iter(root))    # [4, 2, 5, 1, 3, 6]

把递归和迭代两版对照着看,你会理解一个深刻的点:递归不是魔法,它只是把"还没处理完的状态"藏在系统调用栈里;迭代版只是把这个栈搬到了自己手里,变得可控。

4. 层序遍历:BFS 与队列

层序遍历按"一层一层"的顺序访问,用队列实现:出队一个节点,就把它的左右孩子入队。注意下面代码里 for _ in range(len(q)) 的技巧——循环开始时 len(q) 恰好是当前层的节点数,这样能把每一层单独分组。

def level_order(root):
    if root is None:
        return []
    res = []
    q = deque([root])
    while q:
        level = []
        for _ in range(len(q)):   # 处理完整的一层
            node = q.popleft()
            level.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        res.append(level)
    return res

root = build_tree([1, 2, 3, 4, 5, None, 6])
print(level_order(root))
# [[1], [2, 3], [4, 5, 6]]

层序遍历是很多"按层处理"题目的地基,比如求每层最大值、之字形打印、求树的最小深度(第一次遇到叶子时的层数)。会了这一层,那些题都是换汤不换药。

5. 重建二叉树:前序 + 中序

给一棵树的前序和中序遍历结果,能不能把树还原出来?可以,而且思路非常优雅:前序的第一个元素一定是根;在中序里找到根的位置,左边是左子树、右边是右子树;再根据左子树的长度,把前序也切成两半,递归下去。

def build_from_pre_in(preorder, inorder):
    if not preorder:
        return None
    val = preorder[0]
    idx = inorder.index(val)        # 根在中序中的位置
    root = TreeNode(val)
    root.left = build_from_pre_in(
        preorder[1:idx + 1], inorder[:idx])
    root.right = build_from_pre_in(
        preorder[idx + 1:], inorder[idx + 1:])
    return root

root = build_from_pre_in([1, 2, 4, 5, 3, 6], [4, 2, 5, 1, 3, 6])
print(preorder(root))    # [1, 2, 4, 5, 3, 6]
print(inorder(root))     # [4, 2, 5, 1, 3, 6]

注意中序必须有根的位置信息,所以"前序 + 后序"不能唯一确定一棵树(除非是满二叉树)——这是面试里常被追问的知识点。上面代码用 inorder.index 每次 O(n) 查找,数据量大时可以先用字典记录每个值的位置,优化到 O(1)。

顺带一提,build_from_pre_in 这种"切分递归"是很多重建类题目的原型,比如"从中序与后序遍历构造二叉树"(LeetCode 106)——只要把后序的最后一个元素当作根,剩下的逻辑几乎一模一样。掌握一种,另一种五分钟就能写出来。

6. 高频题型:最大深度与对称

最后来两道高频题。最大深度就是"根到最远叶子的边数",递归一行:左右子树深度取大者加一。判断对称则要换个角度——不是比较左右子树,而是比较"镜像位置"的节点,所以递归函数的参数是两个节点。

def max_depth(root):
    if root is None:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

def is_symmetric(root):
    def check(a, b):
        if a is None and b is None:
            return True
        if a is None or b is None:
            return False
        return (a.val == b.val and
                check(a.left, b.right) and   # 镜像位置
                check(a.right, b.left))
    return check(root, root)

root = build_tree([1, 2, 2, 3, 4, 4, 3])
print(max_depth(root))        # 3
print(is_symmetric(root))     # True
root2 = build_tree([1, 2, 2, None, 3, None, 3])
print(is_symmetric(root2))    # False

对称树判断容易踩的坑:直接比较 root.left 和 root.right 是错的——那不是对称,而是左右完全相等。对称要求 a.left 对 b.right、a.right 对 b.left,交叉着比,想想照镜子的感觉就懂了。

再延伸一步:求"最近公共祖先"(LeetCode 236)同样是高频题,思路是在递归中向上一层返回"找到了哪个节点"——左子树找到了就返回左,右子树找到了就返回右,两边都找到了,当前节点就是答案。树的题做多了你会发现,很多难题不过是递归返回值的设计问题。

7. 总结与练习

二叉树的核心就两件事:一是递归地定义(空树、或根加两棵子树),所以几乎所有题都能递归解;二是四种遍历方式(前中后序 + 层序),它们对应不同的访问时机和应用场景。把这两点吃透,二叉树这关就过了大半。

💡 写树的递归函数,先问自己三个问题:递归出口是什么?这一层要做什么?如何把结果传给上一层?三问答完,代码基本就成型了。

练习题: