（算法基础——树）——python树结构使用指南

1. 树的定义与实现

树是一种非线性数据结构，常用于解决层次化数据问题（如路径搜索、二叉树遍历等）。以下是树的两种常见实现方式：

(1) 类（Class）实现 class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val # 节点值 self.left = left # 左子节点 self.right = right # 右子节点 # 示例：构建一个简单的二叉树 root = TreeNode(1) root.left = TreeNode(2) root.right = TreeNode(3) root.left.left = TreeNode(4) (2) 字典实现（适合快速原型设计） tree = { 'val': 1, 'left': { 'val': 2, 'left': {'val': 4, 'left': None, 'right': None}, 'right': None }, 'right': {'val': 3, 'left': None, 'right': None} }

---

2. 树的遍历方法

树的遍历是解决树问题的核心，掌握以下三种遍历方式：

(1) 前序遍历（根-左-右） def preorder(root): if not root: return [] return [root.val] + preorder(root.left) + preorder(root.right) # 示例输出：[1, 2, 4, 3] (2) 中序遍历（左-根-右） def inorder(root): if not root: return [] return inorder(root.left) + [root.val] + inorder(root.right) # 示例输出：[4, 2, 1, 3] (3) 后序遍历（左-右-根） def postorder(root): if not root: return [] return postorder(root.left) + postorder(root.right) + [root.val] # 示例输出：[4, 2, 3, 1] (4) 层序遍历（BFS） from collections import deque def level_order(root): if not root: return [] queue = deque([root]) result = [] 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) result.append(level) return result # 示例输出：[[1], [2, 3], [4]]

---

3. 常见题型与代码模板

以下题型在蓝桥杯中高频出现：

(1) 二叉树的最大深度 def max_depth(root): if not root: return 0 return 1 + max(max_depth(root.left), max_depth(root.right)) (2) 路径总和（LeetCode 112）

判断是否存在根到叶子的路径和为给定值：

def has_path_sum(root, target): if not root: return False if not root.left and not root.right: return root.val == target return has_path_sum(root.left, target - root.val) or has_path_sum(root.right, target - root.val) (3) 二叉树的镜像（反转二叉树） def invert_tree(root): if not root: return None root.left, root.right = invert_tree(root.right), invert_tree(root.left) return root

---

4. 蓝桥杯高频技巧 递归与迭代转换：递归代码简洁但可能栈溢出，需掌握迭代写法（如用栈模拟递归）。处理空节点：始终检查 if not root 避免空指针异常。路径记录：在遍历时通过参数传递路径列表（如 path + [root.val]）。空间优化：某些问题可用Morris遍历实现O(1)空间复杂度。

---

5. 练习题推荐 二叉树的中序遍历（LeetCode 94）对称二叉树（LeetCode 101）从前序与中序遍历序列构造二叉树（LeetCode 105）二叉树的最近公共祖先（LCA，LeetCode 236）

---

掌握以上内容后，可以覆盖蓝桥杯中80%的树相关题目！如果需要更具体的题目解析或优化技巧，请随时告诉我！