Python手把手刷二叉树：从零基础入门到秒杀所有面试笔试题

📌 博客前言

很多同学刚接触算法题时，最怕的就是二叉树：看不懂树的结构、分不清递归在到底怎么绕、迭代遍历写一次错一次。

其实我想告诉你，二叉树是最适合培养递归思维的题型。它不需要太复杂的数据结构基础，只要你掌握了一套通用的思维模板，80% 的二叉树题目都能直接秒杀。本文将全程使用 Python 代码，对零基础极为友好。我们将从最基本的概念出发，一路打通节点构建、核心遍历、经典题型，最后交给你一套“万能解题模板”。一文搞定二叉树刷题，准备好了吗？我们开始！

一、前置知识：到底什么是二叉树？（零基础必看）

alt

1.1 二叉树基础概念

二叉树（Binary Tree）是一种树形数据结构。顾名思义，它的核心定义是：每个节点最多有两个子节点，我们通常称之为“左孩子（Left Child）”和“右孩子（Right Child）”。

核心名词解释：

根节点 (Root)： 树最顶端的那个节点，一切的起源。

叶子节点 (Leaf)： 没有子节点（左右孩子都为空）的节点。

父节点 / 子节点： 上下相连的节点关系。

深度 (Depth) / 高度 (Height)： 深度是指从根节点到某节点的最长简单路径边的条数；高度是指从某节点到叶子节点的最长简单路径边的条数。

1.2 常见二叉树分类（刷题常考）

面试和笔试中，题目经常会加上一些前缀限制条件，你需要对它们了如指掌：

满二叉树： 每一层的节点全部铺满，没有任何空缺。

完全二叉树： 除了最后一层，其余层全部铺满，且最后一层的节点全部靠左排列（堆排序的基础）。

二叉搜索树 (BST)： 这是一个高频面试考点！左子树上的所有节点值都小于根节点值，右子树上的所有节点值都大于根节点值。

平衡二叉树 (AVL)： 任何一个节点的左右子树高度差不超过 1。

1.3 二叉树为什么适合用 Python 刷题？

Python 语法极度简洁，不需要像 C++ 那样手动写析构函数管理内存。它的动态类型和极简的写法，让你能把 100% 的精力放在算法逻辑上，而不是语言特性上。用 Python 写二叉树递归，代码看起来就像伪代码一样清晰。

二、Python代码实现：二叉树节点如何定义？ 2.1 标准树节点结构（LeetCode 官方通用格式） 在力扣 (LeetCode) 上，所有的二叉树题目后台都使用了以下这个标准的类定义。理解它，是刷题的第一步。

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val      # 节点存储的值
        self.left = left    # 指向左子树的指针（默认为空）
        self.right = right  # 指向右子树的指针（默认为空）

2.2 手动构建一棵二叉树（新手实操） 在本地 IDE 调试时，我们需要自己造数据。可以通过实例化 TreeNode 并手动连接它们来构建一棵树：

# 构建节点
root = TreeNode(1)
node2 = TreeNode(2)
node3 = TreeNode(3)

# 拼接节点
root.left = node2
root.right = node3
# 此时构建了一棵根为1，左孩子为2，右孩子为3的简单二叉树

此时构建了一棵根为1，左孩子为2，右孩子为3的简单二叉树

2.3 力扣输入格式说明

新手刷力扣最常见的疑惑：“题目输入明明是个数组 [1,2,3,null,5]，怎么就变成树了？” 力扣后台实际上使用的是层序遍历的方式把数组序列化和反序列化。数组第一个元素是根节点，然后按从左到右、从上到下的顺序依次是左右孩子。遇到 null 说明该位置没有节点。我们写代码时，不需要自己写数组转树的逻辑，直接把传入的 root 当作完整的树形结构处理即可。

三、二叉树核心基石：四种遍历（所有题目的底层逻辑）

二叉树题目的本质，基本都是在做某种遍历。

一句话区分前、中、后序：看“根节点”的访问顺序！

前序遍历： 根 → 左 → 右

中序遍历： 左 → 根 → 右（二叉搜索树的中序遍历是有序数组！）

后序遍历： 左 → 右 → 根

层序遍历： 从上到下、从左到右（广度优先 BFS）

alt

3.1 递归版遍历（最简单，刷题首选）

递归是处理二叉树最自然的方式，以前序遍历为例，代码极简：

Python def preorderTraversal(root): res = [] def dfs(node): if not node: return res.append(node.val) # 中（根） dfs(node.left) # 左 dfs(node.right) # 右

dfs(root)
return res

💡 想要变成中序或后序？只需要把 res.append(node.val) 换个位置即可！

3.2 迭代版遍历（面试必考，不用递归）

面试官有时会为了考察基本功，要求不使用递归。我们需要借助栈 (Stack) 来模拟前中后序，借助队列 (Queue) 来实现层序遍历。

层序遍历（BFS）模板：

Python
import collections
def levelOrder(root):
    if not root: return []
    res = []
    queue = collections.deque([root])
    
    while queue:
        level = []
        size = len(queue)
        for _ in range(size):
            node = queue.popleft()
            level.append(node.val)
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
        res.append(level)
    return res

3.3 遍历核心总结

绝大多数二叉树题目，本质都是在前/中/后序遍历的基础上，改动或者增加一两行代码。 只要吃透了遍历，二叉树就攻克了一半。

四、二叉树解题核心思想：递归三部曲（万能思路） 很多同学写递归靠“玄学”和直觉，结果总是死循环或报错。其实，所有二叉树递归题，都有固定的三步走策略。以后做题，就在脑子里默念这三步：

确定递归终止条件： 最常见的就是 if not root: return ...，保护代码不发生栈溢出。

确定单层递归逻辑： 抛开整棵树，只看当前这个节点（以及它的左右孩子），你需要对它做什么操作？

确定返回值： 这一层递归结束时，你需要向上一层（父节点）返回什么结果？

通用口诀：先想终止，再想单层，最后看返回。

五、LeetCode高频二叉树题型分类 + Python模板代码

5.1 基础简单题（入门必刷）

【二叉树最大深度】 alt

def maxDepth(root):
    if not root: return 0
    left_depth = maxDepth(root.left)
    right_depth = maxDepth(root.right)
    return max(left_depth, right_depth) + 1

解题思路： 后序遍历。左子树最大深度和右子树最大深度找个最大的，加上自己这一层（+1）。

【翻转二叉树 (Mac之父面试被拒题)】

解题思路： 前序或后序遍历，把每个节点的左右孩子对调即可。 alt

def invertTree(root):
    if not root: return None
    root.left, root.right = root.right, root.left # 交换逻辑
    invertTree(root.left)
    invertTree(root.right)
    return root

5.2 路径类题目（笔试高频） 【路径总和】 alt

解题思路： 递归相减。每次往下走一层，目标值减去当前节点值，到了叶子节点看看是否等于 0。

def hasPathSum(root, targetSum):
    if not root: return False
    if not root.left and not root.right: # 到达叶子节点
        return targetSum == root.val
    
    return hasPathSum(root.left, targetSum - root.val) or \
           hasPathSum(root.right, targetSum - root.val)

5.3 二叉搜索树专项（面试重灾区） 【验证二叉搜索树】

解题思路： 利用 BST 特性 —— 中序遍历是一个严格递增的数组。我们记录前一个节点的值，看当前节点是否比它大。

class Solution:
    def __init__(self):
        self.pre = float('-inf') # 记录前一个节点的值
        
    def isValidBST(self, root):
        if not root: return True
        # 左
        left_res = self.isValidBST(root.left)
        # 中
        if root.val <= self.pre:
            return False
        self.pre = root.val
        # 右
        right_res = self.isValidBST(root.right)
        
        return left_res and right_res

5.4 困难高频题（进阶拔高） 【二叉树最近公共祖先 (LCA)】 alt

解题思路： 后序遍历（自底向上寻找）。如果左边找到 p 或 q，右边也找到了，那当前节点就是最近公共祖先。

def lowestCommonAncestor(root, p, q):
    # 终止条件：遇到空，或者遇到了目标节点
    if not root or root == p or root == q: return root
    
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    
    if left and right: return root # 左右各找到一个，当前节点就是祖先
    if left: return left           # 只在左边找到，返回左边的结果
    return right                   # 只在右边找到，返回右边的结果

六、避坑指南：新手写二叉树最容易犯的5个错误

  1. 忘记递归终止条件，出现栈溢出： 永远把 if not root: ... 写在函数第一行。
  2. 分不清前中后序，代码逻辑写反： 牢记：处理当前节点（如打印、比较）的操作放在前面就是前序，中间就是中序，后面就是后序。
  3. 层序遍历不会用队列，遍历顺序混乱： Python 请务必使用 collections.deque，用 popleft() 保证 O(1) 的时间复杂度，千万别用 list.pop(0)。
  4. 二叉搜索树做题忽略区间边界： BST 的左节点不仅要小于父节点，还要小于所有的祖先节点。最好引入最大值/最小值区间或者使用中序遍历。
  5. 分不清树的深度和高度： 深度是从上往下数（用前序），高度是从下往上数（用后序）。 七、二叉树终极万能模板（直接复制刷题） 这份通用的深度优先遍历 (DFS) 递归模板，可以适配 90% 以上的二叉树递归题目，做题时只需改动中间的单层逻辑即可：
def dfs(root):
    # 1. 递归终止条件
    if not root:
        return # [对应返回值，如0, None, [], True等]
        
    # 2. 单层逻辑：前序遍历的代码写在这里
    # ...
    
    left_res = dfs(root.left)
    
    # 2. 单层逻辑：中序遍历的代码写在这里
    # ...
    
    right_res = dfs(root.right)
    
    # 2. 单层逻辑：后序遍历的代码写在这里
    # ...
    
    # 3. 返回结果
    return # [整合 left_res, right_res 和 当前 root 节点的信息]

八、刷题顺序建议（新手不走弯路）

不要在 LeetCode 上盲目随机刷题，请按照以下路线稳扎稳打：

打底： 先吃透三种递归遍历 + 层序遍历模板（4 道题）。

巩固： 刷简单题，如最大深度、最小深度、翻转树、对称二叉树等。

进阶： 攻克路径类、构造树类、公共祖先等中等题。

专项突破： 最后专攻“二叉搜索树 (BST)”专项（插入、删除、修剪、验证）。

📝 博客结尾总结

二叉树的核心不是背代码，是吃透递归思想。

前中后序遍历是一切题目的根基，万变不离其宗。

遇到二叉树，优先思考递归，其次再考虑迭代。

大家刷题遇到二叉树最卡哪道题？评论区留言一起解决～