1. 怎么看二叉树题

二叉树题最重要的不是记住很多遍历代码,而是想清楚:当前节点要从左右子树拿什么信息,又要把什么信息返回给父节点。

链表题考“指针怎么变”,数组题考“下标怎么动”,二叉树题考“递归怎么分工”。每个节点都可以看成一个小问题:

  • 我在当前节点要做什么?
  • 左子树和右子树分别能给我什么?
  • 我要把什么结果返回给上一层?

LeetCode 里的树节点通常长这样:

1
2
3
4
5
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right

刷二叉树题时,我先按题目目标分类:

  • 要输出节点顺序:前序、中序、后序、层序。
  • 要算高度、深度、节点数、是否平衡:重点是递归返回值。
  • 要判断两棵树是否相同、是否对称、是否翻转:重点是成对比较。
  • 要找路径、路径和、所有根到叶子路径:重点是回溯和叶子节点判断。
  • 要构造树:重点是用遍历序列切分左右子树。
  • 遇到 BST:优先利用中序有序、左小右大。
  • 要找最近公共祖先:重点是“左右子树有没有目标节点”。

二叉树递归可以先记一句话:先定义函数含义,再写空节点,再处理左右子树,最后组织返回值。 不要一上来就写代码,先把递归函数当成一个可靠工具。

2. 遍历顺序:递归里当前节点放在哪里

前序、中序、后序的区别,本质是当前节点 root 的处理位置:

1
2
3
前序:中 左 右
中序:左 中 右
后序:左 右 中

144. 二叉树的前序遍历 要返回前序遍历结果。前序适合“先处理当前节点,再处理子树”的场景,比如复制树、序列化树、从根开始传递状态。

1
2
3
4
5
6
7
8
9
10
11
12
13
def preorder_traversal(root: TreeNode | None) -> list[int]:
ans = []

def dfs(node: TreeNode | None) -> None:
if not node:
return

ans.append(node.val)
dfs(node.left)
dfs(node.right)

dfs(root)
return ans

这里 dfs(node) 的含义是:把以 node 为根的子树按前序加入 ans。空节点什么都不做。

94. 二叉树的中序遍历 对普通二叉树只是遍历顺序,对 BST 特别重要,因为 BST 的中序遍历是递增序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
def inorder_traversal(root: TreeNode | None) -> list[int]:
ans = []

def dfs(node: TreeNode | None) -> None:
if not node:
return

dfs(node.left)
ans.append(node.val)
dfs(node.right)

dfs(root)
return ans

145. 二叉树的后序遍历 适合“先拿左右子树结果,再处理当前节点”的题,比如高度、平衡二叉树、删除树、判断子树信息。

1
2
3
4
5
6
7
8
9
10
11
12
13
def postorder_traversal(root: TreeNode | None) -> list[int]:
ans = []

def dfs(node: TreeNode | None) -> None:
if not node:
return

dfs(node.left)
dfs(node.right)
ans.append(node.val)

dfs(root)
return ans

复习遍历时不要只背“三种顺序”。真正做题时要问:当前节点的答案能不能在访问左右子树前确定?如果能,偏前序;如果必须依赖左右子树返回值,偏后序;如果是 BST,先想中序。

3. 迭代遍历:栈保存还没处理完的节点

递归本质上依赖系统调用栈。迭代写法就是自己维护一个栈。

前序迭代比较直观:弹出当前节点,先记录它,再把右孩子、左孩子依次入栈。因为栈是后进先出,左孩子后入栈,反而会先被处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def preorder_traversal(root: TreeNode | None) -> list[int]:
if not root:
return []

stack = [root]
ans = []

while stack:
node = stack.pop()
ans.append(node.val)

if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)

return ans

中序迭代更像“沿着左边一路走到底,然后回头处理节点,再去右边”:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def inorder_traversal(root: TreeNode | None) -> list[int]:
stack = []
ans = []
cur = root

while cur or stack:
while cur:
stack.append(cur)
cur = cur.left

cur = stack.pop()
ans.append(cur.val)
cur = cur.right

return ans

这段代码里,stack 保存的是“左链上还没处理的祖先节点”。当 cur 走到空,说明左边已经到底了,这时弹出最近的祖先处理,再转向它的右子树。

后序迭代可以用“前序变形再反转”:前序是中左右,如果我们改成中右左,最后反转就是左右中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def postorder_traversal(root: TreeNode | None) -> list[int]:
if not root:
return []

stack = [root]
ans = []

while stack:
node = stack.pop()
ans.append(node.val)

if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)

return ans[::-1]

迭代遍历的易错点是入栈顺序。前序要得到中左右,所以入栈时先右后左;后序变形要得到中右左,所以入栈时先左后右。

4. 层序遍历:队列按层推进

层序遍历不是递归主导,而是队列主导。队列里放当前层还没处理的节点;每次循环先固定当前队列长度,这个长度就是这一层的节点数。

102. 二叉树的层序遍历 要按层返回节点值:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
from collections import deque


def level_order(root: TreeNode | None) -> list[list[int]]:
if not root:
return []

q = deque([root])
ans = []

while q:
level = []
size = len(q)

for _ in range(size):
node = q.popleft()
level.append(node.val)

if node.left:
q.append(node.left)
if node.right:
q.append(node.right)

ans.append(level)

return ans

这里 size = len(q) 必须在进入当前层循环之前固定。因为循环过程中会不断把下一层节点加进队列,如果直接 while q 处理,就会把多层混在一起。

很多层序题都是这个框架的变形:

层序题的关键不是“会用队列”,而是明确每次循环处理的是一整层,还是单个节点。如果题目出现“每一层”“最底层”“右视图”“层平均”,优先想层序。

5. 高度、深度、节点数:先设计返回值

二叉树递归题里,返回值设计比代码更重要。

104. 二叉树的最大深度 要求从根到最远叶子节点的节点数。函数可以定义成:max_depth(node) 返回以 node 为根的树的最大深度。

1
2
3
4
5
6
7
8
def max_depth(root: TreeNode | None) -> int:
if not root:
return 0

left = max_depth(root.left)
right = max_depth(root.right)

return max(left, right) + 1

这就是后序:先拿左右子树深度,再加上当前节点这一层。

111. 二叉树的最小深度 容易错。最小深度是到最近叶子节点的深度,叶子节点必须左右孩子都为空。不能简单写 min(left, right) + 1,因为如果某一边为空,深度是 0,但这不是一条到叶子的路径。

1
2
3
4
5
6
7
8
9
10
11
def min_depth(root: TreeNode | None) -> int:
if not root:
return 0

if not root.left:
return min_depth(root.right) + 1

if not root.right:
return min_depth(root.left) + 1

return min(min_depth(root.left), min_depth(root.right)) + 1

比如只有右孩子的一条链,左子树深度是 0,但不能说最小深度是 1,因为根节点不是叶子。

110. 平衡二叉树 要判断每个节点左右子树高度差是否不超过 1。普通写法每个节点都反复算高度,容易变成 O(n2)O(n^2)。更好的写法是让递归返回高度;如果子树已经不平衡,就返回 -1 作为失败信号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def is_balanced(root: TreeNode | None) -> bool:
def height(node: TreeNode | None) -> int:
if not node:
return 0

left = height(node.left)
if left == -1:
return -1

right = height(node.right)
if right == -1:
return -1

if abs(left - right) > 1:
return -1

return max(left, right) + 1

return height(root) != -1

这里 height(node) 的含义不是单纯返回高度,而是:如果以 node 为根的子树平衡,返回高度;否则返回 -1。这就是二叉树题里很常见的“返回值带状态”。

222. 完全二叉树的节点个数 可以普通递归数节点:

1
2
3
4
5
def count_nodes(root: TreeNode | None) -> int:
if not root:
return 0

return count_nodes(root.left) + count_nodes(root.right) + 1

如果利用完全二叉树性质,还可以判断左右边界高度是否相同。若相同,说明这棵子树是满二叉树,节点数直接是 2 ** height - 1;否则继续递归。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def count_nodes(root: TreeNode | None) -> int:
if not root:
return 0

left = root.left
right = root.right
left_height = 1
right_height = 1

while left:
left_height += 1
left = left.left

while right:
right_height += 1
right = right.right

if left_height == right_height:
return 2 ** left_height - 1

return count_nodes(root.left) + count_nodes(root.right) + 1

这类题复习时先问:函数返回的是单个数字,还是带失败信号的数字?当前节点的结果是否依赖左右子树?如果依赖,通常就是后序。

6. 翻转、对称、相同:成对处理左右子树

226. 翻转二叉树 要把每个节点的左右孩子交换。当前节点要做的事很简单:交换左右孩子,然后递归处理左右子树。

1
2
3
4
5
6
7
8
9
def invert_tree(root: TreeNode | None) -> TreeNode | None:
if not root:
return None

root.left, root.right = root.right, root.left
invert_tree(root.left)
invert_tree(root.right)

return root

这题可以前序,也可以后序。只要每个节点都交换一次,顺序并不敏感。

101. 对称二叉树 不是比较一个节点的左孩子和右孩子值这么简单,而是比较两棵子树是否镜像:

  • 左子树的左边,要和右子树的右边相同。
  • 左子树的右边,要和右子树的左边相同。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def is_symmetric(root: TreeNode | None) -> bool:
def compare(left: TreeNode | None, right: TreeNode | None) -> bool:
if not left and not right:
return True

if not left or not right:
return False

if left.val != right.val:
return False

return compare(left.left, right.right) and compare(left.right, right.left)

if not root:
return True

return compare(root.left, root.right)

这题最容易错的是递归方向。如果写成 compare(left.left, right.left),那是在比较同向结构,不是镜像结构。

100. 相同的树 和对称二叉树很像,只是比较方向不同:

1
2
3
4
5
6
7
8
9
10
11
def is_same_tree(p: TreeNode | None, q: TreeNode | None) -> bool:
if not p and not q:
return True

if not p or not q:
return False

if p.val != q.val:
return False

return is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)

成对递归题的关键是把两个节点一起传进去。每一层先处理空节点情况,再比较当前值,最后比较下一层结构。

7. 路径题:路径列表跟着递归进出

路径题通常从根节点出发,走到叶子节点。这里最容易混的是“什么时候算一条完整路径”。只有当前节点是叶子节点时,也就是 not node.left and not node.right,根到当前节点的路径才完整。

257. 二叉树的所有路径 要返回所有根到叶子的路径:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def binary_tree_paths(root: TreeNode | None) -> list[str]:
if not root:
return []

ans = []
path = []

def dfs(node: TreeNode) -> None:
path.append(str(node.val))

if not node.left and not node.right:
ans.append("->".join(path))
else:
if node.left:
dfs(node.left)
if node.right:
dfs(node.right)

path.pop()

dfs(root)
return ans

这里 path.append 和 path.pop 是一对。进入节点时加入路径,离开节点时撤销选择。这和回溯的思想一样。

112. 路径总和 要判断是否存在一条根到叶子路径,使路径和等于 targetSum。可以递归传剩余目标值:

1
2
3
4
5
6
7
8
9
10
def has_path_sum(root: TreeNode | None, target_sum: int) -> bool:
if not root:
return False

if not root.left and not root.right:
return target_sum == root.val

rest = target_sum - root.val

return has_path_sum(root.left, rest) or has_path_sum(root.right, rest)

注意空节点返回 False,不是判断 target_sum == 0。因为题目要求路径必须到叶子节点,空节点不是合法路径。

113. 路径总和 II 要返回所有满足条件的路径。这时不仅要判断,还要保存路径:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def path_sum(root: TreeNode | None, target_sum: int) -> list[list[int]]:
ans = []
path = []

def dfs(node: TreeNode | None, rest: int) -> None:
if not node:
return

path.append(node.val)

if not node.left and not node.right and rest == node.val:
ans.append(path[:])
else:
dfs(node.left, rest - node.val)
dfs(node.right, rest - node.val)

path.pop()

dfs(root, target_sum)
return ans

这里 ans.append(path[:]) 很重要。不能直接 ans.append(path),因为 path 后面会继续被修改,最后答案里的路径会被一起改掉。

路径题的复习重点是三个条件:

  • 是否必须从根开始?
  • 是否必须到叶子结束?
  • 是只判断存在性,还是要返回所有路径?

这三个问题决定递归参数和返回方式。

8. 构造二叉树:用根节点切分左右区间

构造树题的核心是:找到根节点,然后把剩下的节点切成左子树和右子树。

105. 从前序与中序遍历序列构造二叉树 中,前序第一个元素一定是根节点;在中序里找到根节点位置,左边就是左子树,右边就是右子树。

下面用 preorder = [3, 9, 20, 15, 7]、inorder = [9, 3, 15, 20, 7] 演示一次。按“下一步”看:每次先从前序区间拿根,再去中序区间找到根的位置,用左子树数量反推出前序里的左右区间。

前序 + 中序构造二叉树演示 preorder = [3, 9, 20, 15, 7] inorder = [9, 3, 15, 20, 7]
preorder
inorder
阶段 准备 根 - left_size - pre - in -

所以构造树不是凭空造节点,而是不断重复这件事:

1
2
3
前序:拿第一个元素当根
中序:用根的位置切开左右子树
数量:用左子树节点数,反推出前序里的左右边界

为了避免反复切片,可以用下标区间。先用哈希表记录中序值到下标的映射:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def build_tree(preorder: list[int], inorder: list[int]) -> TreeNode | None:
pos = {value: i for i, value in enumerate(inorder)}

def build(pre_l: int, pre_r: int, in_l: int, in_r: int) -> TreeNode | None:
if pre_l > pre_r:
return None

root_val = preorder[pre_l]
root = TreeNode(root_val)
mid = pos[root_val]
left_size = mid - in_l

root.left = build(pre_l + 1, pre_l + left_size, in_l, mid - 1)
root.right = build(pre_l + left_size + 1, pre_r, mid + 1, in_r)

return root

return build(0, len(preorder) - 1, 0, len(inorder) - 1)

这题最容易错的是区间边界。建议固定左闭右闭区间:

1
2
preorder[pre_l ... pre_r]
inorder[in_l ... in_r]

在 Python 代码里我们没有真的切片,而是用下标表示。left_size = mid - in_l 是左子树节点数量。

区间可以照着这张图推:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
preorder:  [root | 左子树 left_size 个 | 右子树]
^
pre_l

inorder: [左子树 | root | 右子树]
^
mid

左子树:
preorder: pre_l + 1 到 pre_l + left_size
inorder: in_l 到 mid - 1

右子树:
preorder: pre_l + left_size + 1 到 pre_r
inorder: mid + 1 到 in_r

106. 从中序与后序遍历序列构造二叉树 类似,只是后序最后一个元素是根节点。仍然用中序切分左右子树。

下面用同一棵树再演示一次:

中序 + 后序构造二叉树演示 inorder = [9, 3, 15, 20, 7] postorder = [9, 15, 7, 20, 3]
inorder
postorder
阶段 准备 根 - left_size - right_size - in - post -

区别只是根节点的位置变了:前序的根在最前面,后序的根在最后面。真正切左右子树,还是靠中序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def build_tree(inorder: list[int], postorder: list[int]) -> TreeNode | None:
pos = {value: i for i, value in enumerate(inorder)}

def build(in_l: int, in_r: int, post_l: int, post_r: int) -> TreeNode | None:
if in_l > in_r:
return None

root_val = postorder[post_r]
root = TreeNode(root_val)
mid = pos[root_val]
left_size = mid - in_l

root.left = build(in_l, mid - 1, post_l, post_l + left_size - 1)
root.right = build(mid + 1, in_r, post_l + left_size, post_r - 1)

return root

return build(0, len(inorder) - 1, 0, len(postorder) - 1)

构造树题不要先背公式。先画出根节点在哪里,再问:左子树有几个节点?右子树从哪里开始?只要数量算对,边界就能推出来。

9. BST:中序有序是第一反应

二叉搜索树 BST 的性质是:左子树所有节点值小于当前节点,右子树所有节点值大于当前节点。它最重要的推论是:中序遍历得到递增序列。

700. 二叉搜索树中的搜索 可以利用大小关系决定往哪边走:

1
2
3
4
5
6
7
8
9
10
11
def search_bst(root: TreeNode | None, val: int) -> TreeNode | None:
if not root:
return None

if root.val == val:
return root

if val < root.val:
return search_bst(root.left, val)

return search_bst(root.right, val)

98. 验证二叉搜索树 不能只检查当前节点和左右孩子。错误写法是:

1
# 错误直觉:只比较 root.left.val < root.val < root.right.val

因为 BST 要求的是整棵左子树都小于根,整棵右子树都大于根。最稳的方式是中序遍历,检查序列是否严格递增:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def is_valid_bst(root: TreeNode | None) -> bool:
prev = None

def inorder(node: TreeNode | None) -> bool:
nonlocal prev

if not node:
return True

if not inorder(node.left):
return False

if prev is not None and node.val <= prev:
return False

prev = node.val

return inorder(node.right)

return inorder(root)

注意是严格递增,所以 node.val <= prev 就不合法。

530. 二叉搜索树的最小绝对差 也是中序。中序相邻两个值的差,才可能是最小差:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def get_minimum_difference(root: TreeNode | None) -> int:
prev = None
ans = float("inf")

def inorder(node: TreeNode | None) -> None:
nonlocal prev, ans

if not node:
return

inorder(node.left)

if prev is not None:
ans = min(ans, node.val - prev)

prev = node.val
inorder(node.right)

inorder(root)
return ans

501. 二叉搜索树中的众数 也可以中序处理,因为相同值会连续出现。只需要维护当前值出现次数和最大次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def find_mode(root: TreeNode | None) -> list[int]:
prev = None
count = 0
max_count = 0
ans = []

def update(value: int) -> None:
nonlocal prev, count, max_count, ans

if prev == value:
count += 1
else:
prev = value
count = 1

if count == max_count:
ans.append(value)
elif count > max_count:
max_count = count
ans = [value]

def inorder(node: TreeNode | None) -> None:
if not node:
return

inorder(node.left)
update(node.val)
inorder(node.right)

inorder(root)
return ans

BST 题先想中序;如果是查找、插入、删除,再想大小关系往左还是往右走。

10. 最近公共祖先:左右子树分别找目标

236. 二叉树的最近公共祖先 给一棵普通二叉树和两个节点 p、q,要求找到它们最近的公共祖先。

递归函数可以定义成:在以 node 为根的子树里寻找 p 或 q,如果找到了就返回对应节点;如果左右子树各找到一个,说明当前节点就是最近公共祖先。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def lowest_common_ancestor(
root: TreeNode | None,
p: TreeNode,
q: TreeNode,
) -> TreeNode | None:
if not root or root == p or root == q:
return root

left = lowest_common_ancestor(root.left, p, q)
right = lowest_common_ancestor(root.right, p, q)

if left and right:
return root

return left if left else right

这段代码的返回值有三种含义:

  • 返回 None:这棵子树里没有 p 或 q。
  • 返回 p 或 q:这棵子树里找到了其中一个目标。
  • 返回某个祖先节点:这棵子树里已经找到了最近公共祖先。

如果左右都非空,说明 p 和 q 分别在当前节点两侧,当前节点就是答案。如果只有一边非空,就把那边的结果往上返回。

235. 二叉搜索树的最近公共祖先 可以利用 BST 性质。若 p 和 q 都小于当前节点,就去左边;都大于当前节点,就去右边;否则当前节点就是分叉点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def lowest_common_ancestor(
root: TreeNode,
p: TreeNode,
q: TreeNode,
) -> TreeNode:
cur = root

while cur:
if p.val < cur.val and q.val < cur.val:
cur = cur.left
elif p.val > cur.val and q.val > cur.val:
cur = cur.right
else:
return cur

普通二叉树的 LCA 依赖后序返回值;BST 的 LCA 依赖大小关系找分叉点。看到题目是不是 BST,要马上切换思路。

11. 复习总览

  • 二叉树题先定义递归函数含义:当前节点要返回什么给父节点。
  • 前序是中左右,适合先处理当前节点;中序是左中右,BST 中序递增;后序是左右中,适合依赖左右子树结果的题。
  • 迭代遍历用栈模拟递归,前序入栈先右后左,中序沿左链压栈。
  • 层序遍历用 deque,每层开始前固定 size = len(q)。
  • 最大深度是 max(left, right) + 1;最小深度要注意空子树不能当作叶子路径。
  • 平衡二叉树可以让递归返回高度,若不平衡返回 -1。
  • 翻转二叉树每个节点交换左右孩子;对称二叉树要比较外侧和内侧。
  • 路径题要判断是否必须到叶子;保存路径时 append 和 pop 要成对出现。
  • 构造树题先找根节点,再用中序位置切分左右子树,重点是区间边界。
  • BST 题先想中序有序;验证 BST 要检查全局递增,不是只看父子节点。
  • 最近公共祖先:普通二叉树看左右子树返回值,BST 看 p、q 和当前节点的大小关系。

二叉树题越往后越像“递归语义设计题”。复习时不要急着背整段代码,先用一句话说清楚函数的返回值。只要返回值定义稳,空节点、左右子树和当前节点的逻辑都会顺下来。

avatar
LittlePyx
小P的学习、研究、生活记录
Follow Me
公告
教育经历
本科:杭州电子科技大学
研究生:电子科技大学

研究方向
AI Agent 开发、计算成像、深度学习、光学

新增:代码随想录算法刷题笔记整理中,按题型与算法模板归纳。
最新文章
网站信息
文章数目 :
18
最后更新时间 :