04-高频算法题精讲-树与递归
本章概述
树是最重要的非线性数据结构之一，在面试中出现频率极高。本章将系统讲解二叉树的各种遍历方式、深度优先搜索（DFS）、广度优先搜索（BFS）以及回溯算法，并通过25+道经典题目帮助读者掌握树相关算法。
本章涵盖：
- 二叉树的前序、中序、后序、层序遍历
- DFS和BFS的应用场景和实现技巧
- 回溯算法的模板和剪枝优化
- 二叉搜索树、平衡树的特性和应用
- 25+道LeetCode高频真题详解
第一节：二叉树基础
1.1 二叉树的定义
二叉树是每个节点最多有两个子节点的树结构。
class TreeNode:
"""二叉树节点定义"""
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
Go语言定义：
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
1.2 二叉树的类型
- 满二叉树：每个节点都有0个或2个子节点
- 完全二叉树：除最后一层外，其他层都是满的，最后一层从左到右填充
- 二叉搜索树（BST）：左子树所有节点值 < 根节点值 < 右子树所有节点值
- 平衡二叉树：任意节点的左右子树高度差不超过1
1.3 树的遍历方式概览
| 遍历方式 | 访问顺序 | 应用场景 |
|---|---|---|
| 前序遍历 | 根-左-右 | 复制树、序列化 |
| 中序遍历 | 左-根-右 | BST有序输出 |
| 后序遍历 | 左-右-根 | 删除树、求高度 |
| 层序遍历 | 逐层访问 | 最短路径、层次信息 |
第二节：深度优先遍历（DFS）
2.1 前序遍历
递归实现：
def preorderTraversal(root: TreeNode) -> list[int]:
"""
前序遍历：根-左-右
"""
result = []
def dfs(node):
if not node:
return
result.append(node.val) # 访问根节点
dfs(node.left) # 遍历左子树
dfs(node.right) # 遍历右子树
dfs(root)
return result
# 时间复杂度: O(n)
# 空间复杂度: O(h)，h为树的高度
迭代实现（使用栈）：
def preorderTraversal(root: TreeNode) -> list[int]:
"""
前序遍历迭代版本
"""
if not root:
return []
result = []
stack = [root]
while stack:
node = stack.pop()
result.append(node.val)
# 先压右子节点，再压左子节点（栈是后进先出）
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return result
# 时间复杂度: O(n)
# 空间复杂度: O(h)
Morris遍历（O(1)空间）：
def preorderTraversal(root: TreeNode) -> list[int]:
"""
Morris前序遍历，空间复杂度O(1)
"""
result = []
curr = root
while curr:
if not curr.left:
# 没有左子树，直接访问并移到右子树
result.append(curr.val)
curr = curr.right
else:
# 找到左子树的最右节点
predecessor = curr.left
while predecessor.right and predecessor.right != curr:
predecessor = predecessor.right
if not predecessor.right:
# 建立线索
result.append(curr.val)
predecessor.right = curr
curr = curr.left
else:
# 已经访问过，删除线索
predecessor.right = None
curr = curr.right
return result
# 时间复杂度: O(n)
# 空间复杂度: O(1)
2.2 中序遍历
递归实现：
def inorderTraversal(root: TreeNode) -> list[int]:
"""
中序遍历：左-根-右
"""
result = []
def dfs(node):
if not node:
return
dfs(node.left) # 遍历左子树
result.append(node.val) # 访问根节点
dfs(node.right) # 遍历右子树
dfs(root)
return result
迭代实现：
def inorderTraversal(root: TreeNode) -> list[int]:
"""
中序遍历迭代版本
"""
result = []
stack = []
curr = root
while curr or stack:
# 一直向左走到底
while curr:
stack.append(curr)
curr = curr.left
# 弹出栈顶节点并访问
curr = stack.pop()
result.append(curr.val)
# 转向右子树
curr = curr.right
return result
# 时间复杂度: O(n)
# 空间复杂度: O(h)
2.3 后序遍历
递归实现：
def postorderTraversal(root: TreeNode) -> list[int]:
"""
后序遍历：左-右-根
"""
result = []
def dfs(node):
if not node:
return
dfs(node.left) # 遍历左子树
dfs(node.right) # 遍历右子树
result.append(node.val) # 访问根节点
dfs(root)
return result
迭代实现：
def postorderTraversal(root: TreeNode) -> list[int]:
"""
后序遍历迭代版本
思路：前序遍历是根-左-右，调整为根-右-左，再反转得到左-右-根
"""
if not root:
return []
result = []
stack = [root]
while stack:
node = stack.pop()
result.append(node.val)
# 先压左子节点，再压右子节点
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return result[::-1] # 反转结果
# 时间复杂度: O(n)
# 空间复杂度: O(h)
2.4 LeetCode 104. 二叉树的最大深度（简单）
题目描述： 给定一个二叉树，找出其最大深度。
解题思路： 使用递归，最大深度 = max(左子树深度, 右子树深度) + 1。
def maxDepth(root: TreeNode) -> int:
"""
计算二叉树最大深度
"""
if not root:
return 0
left_depth = maxDepth(root.left)
right_depth = maxDepth(root.right)
return max(left_depth, right_depth) + 1
# 时间复杂度: O(n)
# 空间复杂度: O(h)
迭代实现（层序遍历）：
from collections import deque
def maxDepth(root: TreeNode) -> int:
"""
使用层序遍历计算深度
"""
if not root:
return 0
queue = deque([root])
depth = 0
while queue:
depth += 1
level_size = len(queue)
for _ in range(level_size):
node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return depth
# 时间复杂度: O(n)
# 空间复杂度: O(w)，w为树的最大宽度
2.5 LeetCode 110. 平衡二叉树（简单）
题目描述： 给定一个二叉树，判断它是否是高度平衡的二叉树。
解题思路： 自底向上递归，同时计算高度和判断是否平衡。
def isBalanced(root: TreeNode) -> bool:
"""
判断是否为平衡二叉树
"""
def get_height(node):
"""
返回高度，如果不平衡返回-1
"""
if not node:
return 0
left_height = get_height(node.left)
if left_height == -1:
return -1
right_height = get_height(node.right)
if right_height == -1:
return -1
# 检查当前节点是否平衡
if abs(left_height - right_height) > 1:
return -1
return max(left_height, right_height) + 1
return get_height(root) != -1
# 时间复杂度: O(n)
# 空间复杂度: O(h)
2.6 LeetCode 226. 翻转二叉树（简单）
题目描述： 翻转一棵二叉树。
解题思路： 递归交换每个节点的左右子树。
def invertTree(root: TreeNode) -> TreeNode:
"""
翻转二叉树
"""
if not root:
return None
# 交换左右子树
root.left, root.right = root.right, root.left
# 递归翻转子树
invertTree(root.left)
invertTree(root.right)
return root
# 时间复杂度: O(n)
# 空间复杂度: O(h)
迭代实现：
from collections import deque
def invertTree(root: TreeNode) -> TreeNode:
"""
翻转二叉树（迭代版本）
"""
if not root:
return None
queue = deque([root])
while queue:
node = queue.popleft()
# 交换左右子树
node.left, node.right = node.right, node.left
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return root
# 时间复杂度: O(n)
# 空间复杂度: O(w)
2.7 LeetCode 101. 对称二叉树（简单）
题目描述： 给定一个二叉树，检查它是否是镜像对称的。
解题思路： 递归判断左右子树是否互为镜像。
def isSymmetric(root: TreeNode) -> bool:
"""
判断二叉树是否对称
"""
def is_mirror(left, right):
"""判断两棵树是否互为镜像"""
if not left and not right:
return True
if not left or not right:
return False
return (left.val == right.val and
is_mirror(left.left, right.right) and
is_mirror(left.right, right.left))
return is_mirror(root, root)
# 时间复杂度: O(n)
# 空间复杂度: O(h)
2.8 LeetCode 543. 二叉树的直径（简单）
题目描述： 给定一棵二叉树，计算它的直径。直径是任意两个节点路径长度中的最大值。
解题思路： 直径 = 某个节点的左子树深度 + 右子树深度。
def diameterOfBinaryTree(root: TreeNode) -> int:
"""
计算二叉树直径
"""
diameter = 0
def depth(node):
nonlocal diameter
if not node:
return 0
left = depth(node.left)
right = depth(node.right)
# 更新直径
diameter = max(diameter, left + right)
return max(left, right) + 1
depth(root)
return diameter
# 时间复杂度: O(n)
# 空间复杂度: O(h)
2.9 LeetCode 236. 二叉树的最近公共祖先（中等）
题目描述： 给定一个二叉树，找到该树中两个指定节点的最近公共祖先。
解题思路： 如果p和q分别在当前节点的左右子树中，则当前节点就是LCA。
def lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
"""
查找最近公共祖先
"""
# 如果当前节点为空，或者等于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)
# 如果左右子树都找到了，说明当前节点是LCA
if left and right:
return root
# 返回非空的那个
return left if left else right
# 时间复杂度: O(n)
# 空间复杂度: O(h)
2.10 LeetCode 124. 二叉树中的最大路径和（困难）
题目描述： 路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点，且不一定经过根节点。
解题思路： 对于每个节点，最大路径和可能是：左子树最大路径 + 节点值 + 右子树最大路径。
def maxPathSum(root: TreeNode) -> int:
"""
计算二叉树的最大路径和
"""
max_sum = float('-inf')
def max_gain(node):
"""
计算从当前节点出发的最大路径和
"""
nonlocal max_sum
if not node:
return 0
# 递归计算左右子树的最大贡献值
# 只有在最大贡献值大于0时才选择对应子节点
left_gain = max(max_gain(node.left), 0)
right_gain = max(max_gain(node.right), 0)
# 当前节点的最大路径和
current_max = node.val + left_gain + right_gain
# 更新全局最大值
max_sum = max(max_sum, current_max)
# 返回当前节点的最大贡献值
return node.val + max(left_gain, right_gain)
max_gain(root)
return max_sum
# 时间复杂度: O(n)
# 空间复杂度: O(h)
第三节：广度优先遍历（BFS）
3.1 层序遍历基础
层序遍历使用队列实现，按层次从上到下、从左到右访问节点。
from collections import deque
def levelOrder(root: TreeNode) -> list[list[int]]:
"""
层序遍历
"""
if not root:
return []
result = []
queue = deque([root])
while queue:
level = []
level_size = len(queue)
for _ in range(level_size):
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为树的最大宽度
Go语言实现：
func levelOrder(root *TreeNode) [][]int {
if root == nil {
return [][]int{}
}
result := [][]int{}
queue := []*TreeNode{root}
for len(queue) > 0 {
level := []int{}
levelSize := len(queue)
for i := 0; i < levelSize; i++ {
node := queue[0]
queue = queue[1:]
level = append(level, node.Val)
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
result = append(result, level)
}
return result
}
3.2 LeetCode 107. 二叉树的层序遍历 II（中等）
题目描述： 给定一个二叉树，返回其节点值自底向上的层序遍历。
解题思路： 正常层序遍历后，反转结果列表。
def levelOrderBottom(root: TreeNode) -> list[list[int]]:
"""
自底向上层序遍历
"""
if not root:
return []
result = []
queue = deque([root])
while queue:
level = []
level_size = len(queue)
for _ in range(level_size):
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[::-1] # 反转结果
# 时间复杂度: O(n)
# 空间复杂度: O(w)
3.3 LeetCode 103. 二叉树的锯齿形层序遍历（中等）
题目描述： 给定一个二叉树，返回其节点值的锯齿形层序遍历。
解题思路： 使用标志位控制每层的遍历方向。
def zigzagLevelOrder(root: TreeNode) -> list[list[int]]:
"""
锯齿形层序遍历
"""
if not root:
return []
result = []
queue = deque([root])
left_to_right = True
while queue:
level = []
level_size = len(queue)
for _ in range(level_size):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
# 根据方向决定是否反转
if not left_to_right:
level.reverse()
result.append(level)
left_to_right = not left_to_right
return result
# 时间复杂度: O(n)
# 空间复杂度: O(w)
3.4 LeetCode 199. 二叉树的右视图（中等）
题目描述： 给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
解题思路： 层序遍历，每层只取最后一个节点。
def rightSideView(root: TreeNode) -> list[int]:
"""
二叉树右视图
"""
if not root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue)
for i in range(level_size):
node = queue.popleft()
# 记录每层的最后一个节点
if i == level_size - 1:
result.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
# 时间复杂度: O(n)
# 空间复杂度: O(w)
3.5 LeetCode 513. 找树左下角的值（中等）
题目描述： 给定一个二叉树，找到该树最底层最左边节点的值。
解题思路： 层序遍历，记录每层的第一个节点。
def findBottomLeftValue(root: TreeNode) -> int:
"""
查找树左下角的值
"""
queue = deque([root])
leftmost = root.val
while queue:
level_size = len(queue)
for i in range(level_size):
node = queue.popleft()
# 记录每层的第一个节点
if i == 0:
leftmost = node.val
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return leftmost
# 时间复杂度: O(n)
# 空间复杂度: O(w)
第四节：二叉搜索树（BST）
4.1 BST的特性
二叉搜索树满足：
- 左子树所有节点的值 < 根节点的值
- 右子树所有节点的值 > 根节点的值
- 左右子树也都是BST
重要性质：
- BST的中序遍历结果是升序序列
- 查找、插入、删除的平均时间复杂度为O(log n)
4.2 LeetCode 98. 验证二叉搜索树（中等）
题目描述： 给定一个二叉树，判断其是否是一个有效的二叉搜索树。
解题思路： 使用中序遍历，检查是否严格递增。
def isValidBST(root: TreeNode) -> bool:
"""
验证二叉搜索树
"""
prev = None
def inorder(node):
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)
# 时间复杂度: O(n)
# 空间复杂度: O(h)
方法二：递归传递范围
def isValidBST(root: TreeNode) -> bool:
"""
使用范围递归验证
"""
def validate(node, min_val, max_val):
if not node:
return True
if node.val <= min_val or node.val >= max_val:
return False
return (validate(node.left, min_val, node.val) and
validate(node.right, node.val, max_val))
return validate(root, float('-inf'), float('inf'))
# 时间复杂度: O(n)
# 空间复杂度: O(h)
4.3 LeetCode 700. 二叉搜索树中的搜索（简单）
题目描述： 给定二叉搜索树（BST）的根节点和一个值，在BST中查找其值等于给定值的节点。
解题思路： 利用BST的性质，根据值的大小决定搜索方向。
def searchBST(root: TreeNode, val: int) -> TreeNode:
"""
在BST中搜索
"""
if not root or root.val == val:
return root
if val < root.val:
return searchBST(root.left, val)
else:
return searchBST(root.right, val)
# 时间复杂度: O(h)
# 空间复杂度: O(h)
迭代实现：
def searchBST(root: TreeNode, val: int) -> TreeNode:
"""
迭代搜索
"""
while root:
if root.val == val:
return root
elif val < root.val:
root = root.left
else:
root = root.right
return None
# 时间复杂度: O(h)
# 空间复杂度: O(1)
4.4 LeetCode 230. 二叉搜索树中第K小的元素（中等）
题目描述： 给定一个二叉搜索树，编写一个函数找出其中第k小的元素。
解题思路： 中序遍历第k个元素就是答案。
def kthSmallest(root: TreeNode, k: int) -> int:
"""
查找第k小的元素
"""
count = 0
result = None
def inorder(node):
nonlocal count, result
if not node or result is not None:
return
inorder(node.left)
count += 1
if count == k:
result = node.val
return
inorder(node.right)
inorder(root)
return result
# 时间复杂度: O(n)最坏情况，O(h+k)平均情况
# 空间复杂度: O(h)
迭代实现：
def kthSmallest(root: TreeNode, k: int) -> int:
"""
迭代中序遍历
"""
stack = []
curr = root
while True:
while curr:
stack.append(curr)
curr = curr.left
curr = stack.pop()
k -= 1
if k == 0:
return curr.val
curr = curr.right
# 时间复杂度: O(h + k)
# 空间复杂度: O(h)
4.5 LeetCode 450. 删除二叉搜索树中的节点（中等）
题目描述： 给定一个二叉搜索树的根节点和一个值，删除该值对应的节点，并保证删除后仍然是合法的BST。
解题思路： 分三种情况处理：
- 叶子节点：直接删除
- 只有一个子节点：用子节点替换
- 有两个子节点：用右子树的最小节点替换
def deleteNode(root: TreeNode, key: int) -> TreeNode:
"""
删除BST中的节点
"""
if not root:
return None
if key < root.val:
root.left = deleteNode(root.left, key)
elif key > root.val:
root.right = deleteNode(root.right, key)
else:
# 找到要删除的节点
if not root.left:
return root.right
if not root.right:
return root.left
# 有两个子节点，找右子树的最小节点
min_node = root.right
while min_node.left:
min_node = min_node.left
# 用最小节点的值替换当前节点
root.val = min_node.val
# 删除最小节点
root.right = deleteNode(root.right, min_node.val)
return root
# 时间复杂度: O(h)
# 空间复杂度: O(h)
4.6 LeetCode 108. 将有序数组转换为二叉搜索树（简单）
题目描述： 给定一个升序数组，将其转换为一棵高度平衡的二叉搜索树。
解题思路： 选择中间元素作为根节点，递归构建左右子树。
def sortedArrayToBST(nums: list[int]) -> TreeNode:
"""
有序数组转BST
"""
def build(left, right):
if left > right:
return None
mid = (left + right) // 2
node = TreeNode(nums[mid])
node.left = build(left, mid - 1)
node.right = build(mid + 1, right)
return node
return build(0, len(nums) - 1)
# 时间复杂度: O(n)
# 空间复杂度: O(log n)
第五节：回溯算法
5.1 回溯算法模板
回溯是一种通过尝试分步去解决问题的算法。在每一步尝试后，如果不满足条件就撤销这一步，尝试其他选择。
基本模板：
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
5.2 LeetCode 46. 全排列（中等）
题目描述： 给定一个不含重复数字的数组 nums，返回其所有可能的全排列。
解题思路： 使用回溯，每次从未使用的数字中选择一个。
def permute(nums: list[int]) -> list[list[int]]:
"""
全排列
"""
result = []
def backtrack(path, used):
# 结束条件
if len(path) == len(nums):
result.append(path[:])
return
for i in range(len(nums)):
if used[i]:
continue
# 做选择
path.append(nums[i])
used[i] = True
# 递归
backtrack(path, used)
# 撤销选择
path.pop()
used[i] = False
backtrack([], [False] * len(nums))
return result
# 测试
print(permute([1,2,3]))
# [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
# 时间复杂度: O(n × n!)
# 空间复杂度: O(n)
5.3 LeetCode 78. 子集（中等）
题目描述： 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集。
解题思路： 每个元素都有选或不选两种选择。
def subsets(nums: list[int]) -> list[list[int]]:
"""
生成所有子集
"""
result = []
def backtrack(start, path):
# 每个状态都是一个有效子集
result.append(path[:])
for i in range(start, len(nums)):
# 选择当前元素
path.append(nums[i])
# 递归
backtrack(i + 1, path)
# 撤销选择
path.pop()
backtrack(0, [])
return result
# 测试
print(subsets([1,2,3]))
# [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]
# 时间复杂度: O(n × 2^n)
# 空间复杂度: O(n)
5.4 LeetCode 39. 组合总和（中等）
题目描述： 给定一个无重复元素的数组 candidates 和一个目标数 target，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。
解题思路： 回溯，注意可以重复选择同一个数字。
def combinationSum(candidates: list[int], target: int) -> list[list[int]]:
"""
组合总和
"""
result = []
def backtrack(start, path, current_sum):
if current_sum == target:
result.append(path[:])
return
if current_sum > target:
return
for i in range(start, len(candidates)):
path.append(candidates[i])
# 可以重复选择，所以还是从i开始
backtrack(i, path, current_sum + candidates[i])
path.pop()
backtrack(0, [], 0)
return result
# 测试
print(combinationSum([2,3,6,7], 7))
# [[2,2,3],[7]]
# 时间复杂度: O(n^(target/min))
# 空间复杂度: O(target/min)
5.5 LeetCode 22. 括号生成（中等）
题目描述： 数字 n 代表生成括号的对数，生成所有可能的并且有效的括号组合。
解题思路： 回溯，维护左右括号的数量。
def generateParenthesis(n: int) -> list[str]:
"""
生成所有有效括号组合
"""
result = []
def backtrack(path, left, right):
"""
path: 当前字符串
left: 剩余左括号数量
right: 剩余右括号数量
"""
if left == 0 and right == 0:
result.append(path)
return
# 可以添加左括号
if left > 0:
backtrack(path + '(', left - 1, right)
# 可以添加右括号（右括号剩余数量必须大于左括号）
if right > left:
backtrack(path + ')', left, right - 1)
backtrack('', n, n)
return result
# 测试
print(generateParenthesis(3))
# ["((()))","(()())","(())()","()(())","()()()"]
# 时间复杂度: O(4^n / sqrt(n))，第n个卡特兰数
# 空间复杂度: O(n)
5.6 LeetCode 17. 电话号码的字母组合（中等）
题目描述： 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
解题思路： 回溯遍历所有可能的组合。
def letterCombinations(digits: str) -> list[str]:
"""
电话号码字母组合
"""
if not digits:
return []
phone_map = {
'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
'6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
}
result = []
def backtrack(index, path):
if index == len(digits):
result.append(path)
return
for letter in phone_map[digits[index]]:
backtrack(index + 1, path + letter)
backtrack(0, '')
return result
# 测试
print(letterCombinations("23"))
# ["ad","ae","af","bd","be","bf","cd","ce","cf"]
# 时间复杂度: O(3^m × 4^n)，m是对应3个字母的数字个数，n是对应4个字母的
# 空间复杂度: O(m + n)
5.7 LeetCode 51. N皇后（困难）
题目描述： n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
解题思路： 回溯，每一行放置一个皇后，检查列、对角线是否冲突。
def solveNQueens(n: int) -> list[list[str]]:
"""
N皇后问题
"""
result = []
board = [['.'] * n for _ in range(n)]
def is_valid(row, col):
"""检查在(row, col)位置放置皇后是否有效"""
# 检查列
for i in range(row):
if board[i][col] == 'Q':
return False
# 检查左上对角线
i, j = row - 1, col - 1
while i >= 0 and j >= 0:
if board[i][j] == 'Q':
return False
i -= 1
j -= 1
# 检查右上对角线
i, j = row - 1, col + 1
while i >= 0 and j < n:
if board[i][j] == 'Q':
return False
i -= 1
j += 1
return True
def backtrack(row):
if row == n:
result.append([''.join(row) for row in board])
return
for col in range(n):
if not is_valid(row, col):
continue
# 放置皇后
board[row][col] = 'Q'
backtrack(row + 1)
# 撤销
board[row][col] = '.'
backtrack(0)
return result
# 时间复杂度: O(n!)
# 空间复杂度: O(n^2)
优化版本（使用集合记录冲突）：
def solveNQueens(n: int) -> list[list[str]]:
"""
N皇后优化版本
"""
result = []
board = [['.'] * n for _ in range(n)]
cols = set() # 记录已占用的列
diag1 = set() # 记录已占用的主对角线(行-列)
diag2 = set() # 记录已占用的副对角线(行+列)
def backtrack(row):
if row == n:
result.append([''.join(row) for row in board])
return
for col in range(n):
if col in cols or row - col in diag1 or row + col in diag2:
continue
# 放置皇后
board[row][col] = 'Q'
cols.add(col)
diag1.add(row - col)
diag2.add(row + col)
backtrack(row + 1)
# 撤销
board[row][col] = '.'
cols.remove(col)
diag1.remove(row - col)
diag2.remove(row + col)
backtrack(0)
return result
# 时间复杂度: O(n!)
# 空间复杂度: O(n)
5.8 LeetCode 79. 单词搜索（中等）
题目描述： 给定一个二维网格和一个单词，找出该单词是否存在于网格中。
解题思路： DFS + 回溯，标记访问过的单元格。
def exist(board: list[list[str]], word: str) -> bool:
"""
单词搜索
"""
m, n = len(board), len(board[0])
visited = [[False] * n for _ in range(m)]
def dfs(i, j, k):
"""
从(i,j)开始搜索word[k:]
"""
if k == len(word):
return True
if (i < 0 or i >= m or j < 0 or j >= n or
visited[i][j] or board[i][j] != word[k]):
return False
# 标记访问
visited[i][j] = True
# 搜索四个方向
found = (dfs(i + 1, j, k + 1) or
dfs(i - 1, j, k + 1) or
dfs(i, j + 1, k + 1) or
dfs(i, j - 1, k + 1))
# 撤销标记
visited[i][j] = False
return found
# 从每个位置开始尝试
for i in range(m):
for j in range(n):
if dfs(i, j, 0):
return True
return False
# 测试
board = [
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
print(exist(board, "ABCCED")) # True
print(exist(board, "SEE")) # True
print(exist(board, "ABCB")) # False
# 时间复杂度: O(m × n × 3^L)，L是单词长度
# 空间复杂度: O(m × n + L)
第六节：树的序列化与反序列化
6.1 LeetCode 297. 二叉树的序列化与反序列化（困难）
题目描述： 设计一个算法来序列化和反序列化二叉树。
解题思路： 使用前序遍历进行序列化，空节点用特殊符号表示。
class Codec:
"""二叉树的序列化与反序列化"""
def serialize(self, root: TreeNode) -> str:
"""序列化二叉树"""
def dfs(node):
if not node:
vals.append('#')
return
vals.append(str(node.val))
dfs(node.left)
dfs(node.right)
vals = []
dfs(root)
return ','.join(vals)
def deserialize(self, data: str) -> TreeNode:
"""反序列化二叉树"""
def dfs():
val = next(vals)
if val == '#':
return None
node = TreeNode(int(val))
node.left = dfs()
node.right = dfs()
return node
vals = iter(data.split(','))
return dfs()
# 时间复杂度: O(n)
# 空间复杂度: O(n)
方法二：层序遍历
class Codec:
"""使用层序遍历进行序列化"""
def serialize(self, root: TreeNode) -> str:
if not root:
return ''
result = []
queue = deque([root])
while queue:
node = queue.popleft()
if node:
result.append(str(node.val))
queue.append(node.left)
queue.append(node.right)
else:
result.append('#')
return ','.join(result)
def deserialize(self, data: str) -> TreeNode:
if not data:
return None
vals = data.split(',')
root = TreeNode(int(vals[0]))
queue = deque([root])
i = 1
while queue:
node = queue.popleft()
if vals[i] != '#':
node.left = TreeNode(int(vals[i]))
queue.append(node.left)
i += 1
if vals[i] != '#':
node.right = TreeNode(int(vals[i]))
queue.append(node.right)
i += 1
return root
# 时间复杂度: O(n)
# 空间复杂度: O(n)
第七节：树的其他经典问题
7.1 LeetCode 114. 二叉树展开为链表（中等）
题目描述： 给定一个二叉树，原地将它展开为一个单链表。
解题思路： 后序遍历，从右到左处理。
def flatten(root: TreeNode) -> None:
"""
展开二叉树为链表
"""
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)
# 时间复杂度: O(n)
# 空间复杂度: O(h)
7.2 LeetCode 437. 路径总和 III（中等）
题目描述： 给定一个二叉树，找到路径总和等于给定值的路径总数。路径不需要从根节点开始，也不需要在叶子节点结束。
解题思路： 使用前缀和 + 哈希表。
def pathSum(root: TreeNode, targetSum: int) -> int:
"""
路径总和III
"""
prefix_sum = {0: 1} # 前缀和 -> 出现次数
count = 0
def dfs(node, current_sum):
nonlocal count
if not node:
return
current_sum += node.val
# 查找是否存在前缀和
count += prefix_sum.get(current_sum - targetSum, 0)
# 更新前缀和
prefix_sum[current_sum] = prefix_sum.get(current_sum, 0) + 1
# 递归
dfs(node.left, current_sum)
dfs(node.right, current_sum)
# 回溯：移除当前路径的前缀和
prefix_sum[current_sum] -= 1
dfs(root, 0)
return count
# 时间复杂度: O(n)
# 空间复杂度: O(n)
7.3 LeetCode 105. 从前序与中序遍历序列构造二叉树（中等）
题目描述： 给定一棵树的前序遍历和中序遍历，构造二叉树。
解题思路： 前序遍历的第一个元素是根节点，在中序遍历中找到根节点的位置，左边是左子树，右边是右子树。
def buildTree(preorder: list[int], inorder: list[int]) -> TreeNode:
"""
从前序和中序遍历构造二叉树
"""
if not preorder:
return None
# 构建中序遍历的值到索引的映射
inorder_map = {val: i for i, val in enumerate(inorder)}
def build(pre_left, pre_right, in_left, in_right):
if pre_left > pre_right:
return None
# 前序遍历的第一个节点是根节点
root_val = preorder[pre_left]
root = TreeNode(root_val)
# 在中序遍历中找到根节点的位置
in_root_index = inorder_map[root_val]
# 左子树的大小
left_size = in_root_index - in_left
# 递归构建左右子树
root.left = build(pre_left + 1, pre_left + left_size,
in_left, in_root_index - 1)
root.right = build(pre_left + left_size + 1, pre_right,
in_root_index + 1, in_right)
return root
return build(0, len(preorder) - 1, 0, len(inorder) - 1)
# 时间复杂度: O(n)
# 空间复杂度: O(n)
7.4 LeetCode 617. 合并二叉树（简单）
题目描述： 给定两个二叉树，将它们合并为一个新的二叉树。合并规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值。
解题思路： 递归合并两棵树。
def mergeTrees(root1: TreeNode, root2: TreeNode) -> TreeNode:
"""
合并二叉树
"""
if not root1:
return root2
if not root2:
return root1
# 创建新节点
merged = TreeNode(root1.val + root2.val)
# 递归合并左右子树
merged.left = mergeTrees(root1.left, root2.left)
merged.right = mergeTrees(root1.right, root2.right)
return merged
# 时间复杂度: O(min(m, n))
# 空间复杂度: O(min(m, n))
本章总结
本章系统讲解了树与递归的核心知识点：
遍历方式总结：
| 遍历方式 | 递归实现 | 迭代实现 | Morris遍历 | 应用场景 |
|---|---|---|---|---|
| 前序 | 简单 | 栈 | 可实现 | 复制树、序列化 |
| 中序 | 简单 | 栈 | 可实现 | BST有序输出 |
| 后序 | 简单 | 栈+标记 | 可实现 | 删除树、求高度 |
| 层序 | 队列 | 队列 | 不适用 | 最短路径、层次 |
核心算法技巧：
DFS（深度优先搜索）
- 递归是最自然的实现方式
- 注意递归终止条件和返回值
- 善用全局变量或闭包传递状态
BFS（广度优先搜索）
- 使用队列实现层序遍历
- 适合求最短路径、层次信息
- 空间复杂度取决于树的宽度
BST特性应用
- 中序遍历得到有序序列
- 利用大小关系减少搜索空间
- 平衡BST的查找效率为O(log n)
回溯算法
- 做选择 -> 递归 -> 撤销选择
- 注意剪枝优化
- 使用visited数组或集合避免重复
复杂度分析要点：
- 递归的空间复杂度取决于递归深度（树的高度）
- 完全二叉树高度为O(log n)，最坏情况（链状）为O(n)
- Morris遍历可以达到O(1)空间复杂度
常见题型：
- 树的遍历（前中后序、层序）
- 树的属性（深度、直径、平衡性）
- 路径问题（路径和、最近公共祖先）
- 修改树结构（翻转、合并、展开）
- BST专题（验证、查找、插入删除）
- 回溯问题（全排列、子集、组合）
下一章讲解图与拓扑排序算法，包括图的遍历、最短路径、拓扑排序和并查集。