LeetCode 二叉树专题：19道题完整学习指南（Python）
这套题涵盖了二叉树面试的主要考点：DFS、BFS、递归、回溯、二叉搜索树（BST）、分治、树形动态规划、前缀和。
建议采用以下学习方式：
- 先理解递归框架：弄明白函数输入什么、返回什么、什么时候处理当前节点。
- 学习一类题，掌握一个模板：不要每道题都背一套代码。
- 先自己写递归，再研究迭代：除层序遍历外，递归通常更容易理解。
- 学会区分递归返回值和全局答案：这是直径、最大路径和、最近公共祖先等题目的关键。
- 做完一道题，再尝试不用参考答案写一遍：能够独立复现，才算真正掌握。
一、建议的学习顺序
| 阶段 | 题目 | 学习重点 |
|---|---|---|
| ① 遍历基础 | 前序、中序、后序、层序 | DFS、BFS |
| ② 基础递归 | 最大深度、翻转、对称、路径总和 | 递归函数设计 |
| ③ 二叉搜索树 | 验证BST、第K小、有序数组构造BST | 中序有序、分治 |
| ④ 进阶递归 | 右视图、最近公共祖先、展开链表 | 信息传递、指针修改 |
| ⑤ 树形DP | 直径、最大路径和 | 后序遍历、全局最优 |
| ⑥ 路径与构造 | 路径总和III、前中序构造、中后序构造 | 前缀和、哈希表、区间分治 |
二、先理解二叉树的核心结构
LeetCode 的二叉树节点通常已经定义好：
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
一棵二叉树：
二叉树递归的基本思想：
一棵树可以拆成根节点、左子树和右子树。左、右子树本身又是二叉树。
因此很多问题可以用以下结构解决：
def dfs(root):
if not root:
return ...
left = dfs(root.left)
right = dfs(root.right)
# 根据左右子树的信息解决当前问题
return ...
最重要：理解两类递归
第一类：遍历型递归
关注访问过程，通常通过外部列表或变量记录答案。
def dfs(root):
if not root:
return
# 处理当前节点
dfs(root.left)
dfs(root.right)
适用于前中后序遍历、收集节点等问题。
第二类：分解型递归
关注子问题的返回结果，当前节点利用左右子树的结果进行计算。
def dfs(root):
if not root:
return 0
left = dfs(root.left)
right = dfs(root.right)
return max(left, right) + 1
适用于最大深度、直径、最大路径和等问题。
接下来每题均按照 思路 → 代码 → 复杂度 → 易错点 讲解。
第一阶段：四种遍历
01LeetCode 144二叉树的前序遍历
思路
先访问当前节点，再遍历左子树，最后遍历右子树。
class Solution:
def preorderTraversal(self, root):
ans = []
def dfs(node):
if not node:
return
ans.append(node.val)
dfs(node.left)
dfs(node.right)
dfs(root)
return ans
执行顺序：
1
/ \
2 3
/ \
4 5
结果：[1, 2, 4, 5, 3]
时间复杂度：O(n)，每个节点访问一次。
空间复杂度：O(h) 递归栈，加上 O(n) 结果列表。h 是树高。
记忆方式：先记录，再递归。
02LeetCode 94二叉树的中序遍历
思路
先遍历左子树，再访问当前节点，最后遍历右子树。
class Solution:
def inorderTraversal(self, root):
ans = []
def dfs(node):
if not node:
return
dfs(node.left)
ans.append(node.val)
dfs(node.right)
dfs(root)
return ans
对于上面的树，结果为：
[4, 2, 5, 1, 3]
时间复杂度：O(n)。
核心性质：二叉搜索树的中序遍历结果是非递减序列；如果节点值互不相同，则严格递增。
这是后面验证BST和求第K小元素的基础。
03LeetCode 145二叉树的后序遍历
思路
先处理左右子树，最后处理当前节点。
class Solution:
def postorderTraversal(self, root):
ans = []
def dfs(node):
if not node:
return
dfs(node.left)
dfs(node.right)
ans.append(node.val)
dfs(root)
return ans
结果：
[4, 5, 2, 3, 1]
时间复杂度：O(n)。
重点：后序遍历特别适合需要先知道左右子树答案，再计算当前节点答案的题目。
例如：最大深度、直径、最大路径和。
04LeetCode 102二叉树的层序遍历
思路
逐层访问节点，必须知道每一层的节点数量。
使用 deque 实现队列：
from collections import deque
class Solution:
def levelOrder(self, root):
if not root:
return []
queue = deque([root])
ans = []
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)
ans.append(level)
return ans
示例：
1
/ \
2 3
/ \
4 5
输出：[[1], [2, 3], [4, 5]]
时间复杂度：O(n)。
空间复杂度：O(n)，用于队列和输出。
最关键的一行：
for _ in range(len(queue)):
这里的 len(queue) 在本层循环开始时确定。即使循环中不断加入下一层节点，这一轮也只处理当前层。
第二阶段：基础递归
05LeetCode 104二叉树的最大深度
思路
当前节点的最大深度：
空节点深度为0。
class Solution:
def maxDepth(self, root):
if not root:
return 0
left = self.maxDepth(root.left)
right = self.maxDepth(root.right)
return max(left, right) + 1
理解递归展开：
1
/ \
2 3
/
4
节点4：max(0,0)+1 = 1
节点2：max(1,0)+1 = 2
节点3：max(0,0)+1 = 1
节点1：max(2,1)+1 = 3
时间 O(n)，递归栈 O(h)。
这里的 +1 代表当前节点本身。
06LeetCode 226翻转二叉树
思路
每个节点只需要交换左右孩子，然后递归处理子树。
class Solution:
def invertTree(self, root):
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)。
注意：交换以后，root.left 已经是原来的右子树，但左右都会递归处理，因此不影响正确性。
07LeetCode 101对称二叉树
思路
一棵树对称意味着：
- 左子树的根与右子树的根相等。
- 左子树的左孩子与右子树的右孩子对称。
- 左子树的右孩子与右子树的左孩子对称。
class Solution:
def isSymmetric(self, root):
def check(left, right):
if not left and not right:
return True
if not left or not right:
return False
if left.val != right.val:
return False
return (
check(left.left, right.right)
and check(left.right, right.left)
)
return check(root.left, root.right) if root else True
时间 O(n)，递归栈 O(h)。
容易出错的地方是递归比较方向：左左对右右，左右对右左，而不是对应位置比较。
08LeetCode 112路径总和
思路
判断是否存在一条从根节点到叶节点的路径，使所有节点值之和等于 targetSum。
每往下一层，将目标值减去当前节点值。
class Solution:
def hasPathSum(self, root, targetSum):
if not root:
return False
if not root.left and not root.right:
return root.val == targetSum
remain = targetSum - root.val
return (
self.hasPathSum(root.left, remain)
or self.hasPathSum(root.right, remain)
)
例如：
5
/ \
4 8
/
11
/ \
7 2
targetSum = 22，存在路径 5 → 4 → 11 → 2，返回 True。
时间 O(n)，递归栈 O(h)。
易错点：必须到达叶节点才能判断成功，不能在中途累计和等于目标值时立即返回 True。
第三阶段：二叉搜索树 BST
在开始这三道题之前，必须理解 BST 的核心性质：
BST 的重要性质是：
对于节点值不重复的 BST：
中序遍历必然得到严格递增序列。
例如上图：
2, 4, 6, 8, 10, 12, 14
09LeetCode 98验证二叉搜索树
思路一：利用上下界（推荐）
对于每个节点，不只是判断它与直接孩子的大小，还要判断它是否处在整个祖先节点确定的合法区间内。
class Solution:
def isValidBST(self, root):
def dfs(node, low, high):
if not node:
return True
if not (low < node.val < high):
return False
return (
dfs(node.left, low, node.val)
and dfs(node.right, node.val, high)
)
return dfs(root, float('-inf'), float('inf'))
例如：
5
/ \
1 7
/ \
3 8
虽然 3 < 7，但节点3在5的右子树中，应该大于5。因此这不是BST。
递归到3时，合法区间为 (5, 7)，检查失败。
思路二：中序遍历
只需要判断中序序列是否严格递增。
class Solution:
def isValidBST(self, root):
prev = float('-inf')
def dfs(node):
nonlocal prev
if not node:
return True
if not dfs(node.left):
return False
if node.val <= prev:
return False
prev = node.val
return dfs(node.right)
return dfs(root)
时间 O(n)，递归栈 O(h)。
面试推荐： 两种方法都应该掌握。上下界法更能体现对BST定义的理解，中序法可以复用于后面的第K小元素。
10LeetCode 230二叉搜索树中第K小的元素
思路
由于BST中序有序，只要中序访问到第K个节点，即可得到答案。
class Solution:
def kthSmallest(self, root, k):
stack = []
cur = root
while cur or stack:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
k -= 1
if k == 0:
return cur.val
cur = cur.right
示例：
5
/ \
3 6
/ \
2 4
/
1
中序序列 [1,2,3,4,5,6]，当 k=3 时，答案为3。
时间复杂度：O(h+k)，最多访问到第K小的节点；空间 O(h)。
其中 h 是树高。
为什么使用迭代？ 可以在找到第K个节点时立即停止，不必遍历剩余节点。
11LeetCode 108将有序数组转换为二叉搜索树
思路
输入数组有序，要求生成高度平衡的BST。
每次选择中间元素作为根节点：
- 左半部分构造左子树。
- 右半部分构造右子树。
- 不断递归。
class Solution:
def sortedArrayToBST(self, nums):
def build(left, right):
if left > right:
return None
mid = (left + right) // 2
root = TreeNode(nums[mid])
root.left = build(left, mid - 1)
root.right = build(mid + 1, right)
return root
return build(0, len(nums) - 1)
示例：
输入：[-10, -3, 0, 5, 9]
选择中间值 0 为根：
0
/ \
-10 5
\ \
-3 9
这是其中一种合法结果。
时间 O(n)，递归栈 O(log n)。
重要思维：构造一棵树时，要考虑怎样确定根节点，再递归确定左右子树。这种分治思想也适用于后面的两道遍历序列重建题。
第四阶段：进阶递归与树结构修改
12LeetCode 199二叉树的右视图
思路
从右边观察二叉树，每一层只能看到最右侧的一个节点。
因此直接使用层序遍历，记录每层最后一个节点。
from collections import deque
class Solution:
def rightSideView(self, root):
if not root:
return []
queue = deque([root])
ans = []
while queue:
size = len(queue)
for i in range(size):
node = queue.popleft()
if i == size - 1:
ans.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return ans
示例：
1 ← 1
/ \
2 3 ← 3
\ \
5 4 ← 4
结果：[1, 3, 4]
时间 O(n)，队列空间最坏 O(n)。
知识迁移：层序遍历解决“每层最大值、每层平均值、每层最后一个节点”等问题时，通常只需修改当前层的处理逻辑。
13LeetCode 236二叉树的最近公共祖先
思路
最近公共祖先（LCA）是指同时拥有节点p、q作为后代（允许节点本身）的最深节点。
递归判断：
- 当前节点为空，返回 None。
- 当前节点是p或q，返回当前节点。
- 分别在左右子树寻找p或q。
- 如果左右都找到了，则当前节点是最近公共祖先。
- 如果只有一侧找到，就将这一侧的结果向上返回。
class Solution:
def lowestCommonAncestor(self, root, p, q):
if not root or root == p or root == q:
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if left and right:
return root
return left if left else right
例如：
3
/ \
5 1
/ \ / \
6 2 0 8
/ \
7 4
- p=5，q=1：最近公共祖先为3。
- p=5，q=4：最近公共祖先为5。
时间 O(n)，递归栈 O(h)。
难点不在代码，而在理解递归函数返回什么。
它返回的是当前子树中找到的目标节点或最近公共祖先。如果两个目标分别来自左右子树，则当前节点就是LCA。
这道题默认题目保证p和q都存在于树中。
14LeetCode 114二叉树展开为链表
思路
将二叉树按前序遍历顺序展开为单向链表，要求：
- 使用原来的 TreeNode。
- 所有
left = None。 - 通过
right指向下一个节点。 - 不能新建一条链表代替原树。
可以利用 右→左→根 的遍历顺序，从链表尾部往前连接。
class Solution:
def flatten(self, root):
prev = None
def dfs(node):
nonlocal prev
if not node:
return
dfs(node.right)
dfs(node.left)
node.right = prev
node.left = None
prev = node
dfs(root)
例如：
原树：
1
/ \
2 5
/ \ \
3 4 6
展开：
1 → 2 → 3 → 4 → 5 → 6
为什么先右后左？
目标链表是前序顺序：
根 → 左 → 右
但我们是倒着连接的，因此处理顺序必须是：
右 → 左 → 根
每次执行：
node.right = prev
prev = node
就是将当前节点插到已构造链表的头部。
时间 O(n)，递归栈 O(h)，不额外创建链表节点。
第五阶段：树形动态规划（重点）
这一阶段的两道题非常重要。
树形DP（Tree Dynamic Programming）的特点是：
先递归计算左右子树的信息，再用这些信息更新当前节点的结果。
和普通递归最大的区别是，经常需要区分两个概念：
dfs()的返回值：当前子树能够提供给父节点什么。ans：遍历整棵树过程中找到的全局最优答案。
15LeetCode 543二叉树的直径
题目要求
求任意两个节点之间最长路径的边数。这条路径不一定经过根节点。
思路
对于任意节点，如果最长路径经过它，那么路径长度为：
而当前节点向父节点返回的深度为：
代码
class Solution:
def diameterOfBinaryTree(self, root):
ans = 0
def dfs(node):
nonlocal ans
if not node:
return 0
left = dfs(node.left)
right = dfs(node.right)
ans = max(ans, left + right)
return max(left, right) + 1
dfs(root)
return ans
为什么 ans 使用 left + right？
因为路径可以从左子树的最深节点，经过当前节点，再到右子树的最深节点。
为什么 dfs 只能返回 max(left, right) + 1？
因为向父节点延伸时，只能选择当前节点的一侧，否则会产生分叉，不再是一条简单路径。
时间 O(n)，递归栈 O(h)。
16LeetCode 124二叉树中的最大路径和
这道题和直径非常相似，但存在几个区别：
- 计算的是节点值之和，不是边数。
- 节点值可以为负数。
- 路径可以从任意节点开始，到任意节点结束。
思路
对于当前节点，分别计算左右子树向上能够提供的最大贡献。
如果某个子树的贡献是负数，那么不如不选择它：
left = max(0, dfs(node.left))
right = max(0, dfs(node.right))
经过当前节点的路径最大值：
返回父节点的最大单侧贡献：
代码
class Solution:
def maxPathSum(self, root):
ans = float('-inf')
def dfs(node):
nonlocal ans
if not node:
return 0
left = max(0, dfs(node.left))
right = max(0, dfs(node.right))
ans = max(
ans,
node.val + left + right
)
return node.val + max(left, right)
dfs(root)
return ans
示例：
-10
/ \
9 20
/ \
15 7
最大路径：
15 → 20 → 7
最大路径和：
时间 O(n)，递归栈 O(h)。
为什么全局答案初始化为负无穷？
因为所有节点可能都是负数：
-3
正确答案是 -3，不是0。
如果把 ans 初始化为0，就会出现错误。
直径与最大路径和对比
| 特征 | 直径 | 最大路径和 |
|---|---|---|
| 计算对象 | 路径边数 | 路径节点值之和 |
| DFS返回 | 最大单侧深度 | 最大单侧贡献 |
| 全局答案 | left + right |
val + left + right |
| 负数处理 | 无需处理 | max(0, dfs(...)) |
| 递归位置 | 后序 | 后序 |
两者的核心递归结构几乎一致。真正需要理解的，是为什么全局答案可以包含左右两侧，而返回父节点时只能选择一侧。
第六阶段：路径前缀和与二叉树构造
17LeetCode 437路径总和 III
这道题比前面的路径总和更难，因为：
- 路径可以从任意节点开始。
- 路径可以在任意节点结束。
- 路径必须沿父节点到子节点方向向下。
- 需要统计符合要求的路径数量，而非判断是否存在。
思路一：双重DFS（容易理解）
对于每个节点，把它当作路径起点，统计从它出发的合法路径。
然后递归考虑每个节点作为起点的情况。
class Solution:
def pathSum(self, root, targetSum):
def count(node, remain):
if not node:
return 0
ans = 1 if node.val == remain else 0
ans += count(node.left, remain - node.val)
ans += count(node.right, remain - node.val)
return ans
if not root:
return 0
return (
count(root, targetSum)
+ self.pathSum(root.left, targetSum)
+ self.pathSum(root.right, targetSum)
)
这种方法简单，但有重复计算。
时间复杂度：最坏 O(n²)，平衡树约 O(n log n)。
思路二：前缀和 + 哈希表（推荐掌握）
从根节点到当前节点的累计和记作 current。
如果某一段向下路径之和为 targetSum，那么必须满足：
转换为：
因此，我们只需要知道当前路径上有多少个历史前缀和等于 current - targetSum。
from collections import defaultdict
class Solution:
def pathSum(self, root, targetSum):
prefix = defaultdict(int)
prefix[0] = 1
def dfs(node, current):
if not node:
return 0
current += node.val
ans = prefix[current - targetSum]
prefix[current] += 1
ans += dfs(node.left, current)
ans += dfs(node.right, current)
prefix[current] -= 1
return ans
return dfs(root, 0)
为什么需要回溯？
prefix[current] -= 1
这行非常重要。
prefix 存储的是当前根到节点路径上的前缀和，不是整棵树所有节点的前缀和。
当左子树访问结束，开始访问右子树时，不能将左子树中的路径前缀和保留下来。
否则可能把左子树中的节点和右子树中的节点错误地拼接成一条路径。
时间复杂度：期望 O(n)，基于哈希表操作均摊 O(1)。
空间复杂度：O(h)，用于递归栈和当前路径上的前缀和计数。
复杂度补充（对上面的原版代码作严谨说明）： 由于
defaultdict在读取不存在的键时会创建新键，并且上面的写法没有删除减至 0 的键，所以这份原样代码的哈希表空间最坏可达 O(n)。若需要严格实现 O(h) 辅助空间，应将查询改为prefix.get(current - targetSum, 0)，并在回溯时令prefix[current] -= 1后，当计数为 0 就执行del prefix[current]，使哈希表只保留当前路径所需的键。这样不改变算法思路，也不改变期望 O(n) 时间复杂度。
这道题的核心是：用前缀和把“任意起点的路径求和”变成“查找历史累计和”。
18LeetCode 105从前序与中序遍历序列构造二叉树
前序：根 → 左 → 右。
中序：左 → 根 → 右。
题目保证节点值互不相同，因此可以唯一构造二叉树。
思路
例如：
前序：[3, 9, 20, 15, 7]
中序：[9, 3, 15, 20, 7]
前序第一个元素3就是整棵树的根。
在中序数组中找到3：
[9] | 3 | [15, 20, 7]
左 根 右
左子树1个节点，右子树3个节点。
递归构造即可。
代码
class Solution:
def buildTree(self, preorder, inorder):
index = {
val: i for i, val in enumerate(inorder)
}
def build(preLeft, inLeft, size):
if size == 0:
return None
rootVal = preorder[preLeft]
root = TreeNode(rootVal)
mid = index[rootVal]
leftSize = mid - inLeft
rightSize = size - leftSize - 1
root.left = build(
preLeft + 1,
inLeft,
leftSize
)
root.right = build(
preLeft + 1 + leftSize,
mid + 1,
rightSize
)
return root
return build(0, 0, len(preorder))
执行结果：
3
/ \
9 20
/ \
15 7
时间 O(n)：利用哈希表快速定位中序节点。
空间 O(n)：哈希表、递归栈和构造的节点。
最难的地方是计算左右子树的区间。建议画出数组，并标记根节点与左右子树范围，再写递归。
19LeetCode 106从中序与后序遍历序列构造二叉树
这道题与上一题几乎完全相同。
区别在于：
- 前序遍历的第一个元素是根。
- 后序遍历的最后一个元素是根。
思路
中序：[9, 3, 15, 20, 7]
后序：[9, 15, 7, 20, 3]
后序最后一个元素3为根。
根据中序数组划分左右子树：
[9] | 3 | [15, 20, 7]
代码
class Solution:
def buildTree(self, inorder, postorder):
index = {
val: i for i, val in enumerate(inorder)
}
def build(inLeft, postLeft, size):
if size == 0:
return None
rootVal = postorder[postLeft + size - 1]
root = TreeNode(rootVal)
mid = index[rootVal]
leftSize = mid - inLeft
rightSize = size - leftSize - 1
root.left = build(
inLeft,
postLeft,
leftSize
)
root.right = build(
mid + 1,
postLeft + leftSize,
rightSize
)
return root
return build(0, 0, len(inorder))
时间 O(n)，辅助空间 O(n)。
两道构造题的对比
| 判断依据 | 前序 + 中序 | 中序 + 后序 |
|---|---|---|
| 根节点的位置 | 前序第一个 | 后序最后一个 |
| 左右子树范围 | 中序确定 | 中序确定 |
| 核心方法 | 分治递归 | 分治递归 |
| 时间复杂度 | O(n) | O(n) |
一定记住：中序遍历是确定左右子树划分的关键。
仅有前序和后序遍历，在一般二叉树中不能保证唯一重建。
七、19道题的知识点总结
做完这些题后，应该形成下面这套判断体系。
1. 看到题目，如何选择解法？
2. 最值得记住的5个代码模式
| 模式 | 核心代码 | 代表题 |
|---|---|---|
| DFS遍历 | dfs(left); dfs(right) |
前、中、后序 |
| BFS层序 | for _ in range(len(queue)) |
层序、右视图 |
| 递归汇总 | return max(left, right) + 1 |
最大深度 |
| 树形DP | ans = max(ans, left + right) |
直径 |
| 分治构造 | root.left = build(...) |
105、106、108 |
3. 重点掌握程度
八、推荐的5天学习安排
| 天数 | 学习内容 | 目标 |
|---|---|---|
| Day 1 | 前序、中序、后序、层序、最大深度 | 熟悉DFS、BFS |
| Day 2 | 翻转、对称、路径总和、验证BST | 熟悉递归边界与状态 |
| Day 3 | 第K小、有序数组构造BST、右视图、LCA | 理解BST、分治和递归返回值 |
| Day 4 | 展开链表、直径、最大路径和 | 掌握指针修改和树形DP |
| Day 5 | 路径总和III、两道构造题 | 理解前缀和、回溯及区间划分 |
最后建议做一次闭卷练习，至少独立写出 层序遍历、最大深度、验证BST、最近公共祖先、二叉树直径和前中序构造二叉树 这6道题。
对于求职笔试和技术面试，二叉树专题真正需要建立的思维是：
向下传递信息用递归参数，向上汇总信息用递归返回值；逐层访问用BFS；求全局最优往往需要后序遍历配合全局变量；构造树则优先考虑递归分治。
理解这套方法，比单独记住19份答案更有价值。