树的代码题分析与解决指南

---

一、树的基本概念回顾

1. 树的结构特点

树是由节点(Node)和边(Edge)组成的非线性数据结构，具有层级关系：

• 每个节点有零个或多个子节点
• 每个节点只有一个父节点（（根节点除外）
• 没有环路的连通图

2. 常见术语

• 根节点：没有父节点的节点
• 叶子节点：没有子节点的节点
• 深度：从根节点到该节点的路径长度
• 高度：从该节点到叶子节点的最长路径长度
• 度：节点拥有的子节点数

二、解决树问题的核心方法

1. 遍历方法

遍历是解决树问题的基础，分为两类：

深度优先遍历(DFS)

广度优先遍历(BFS)

遍历实现对比

遍历方式	递归实现	迭代实现	适用场景
前序遍历	简单	使用栈	复制树、序列化
中序遍历	简单	使用栈	二叉搜索树有序输出
后序遍历	简单	使用栈或反转技巧	删除树、表达式计算
层序遍历	不常用	使用队列	按层处理、找最短路径

2. 递归与分治

树的递归特性：

• 每个子树都是更小的树
• 大多数树问题可用递归分解为：
  1. 处理当前节点
  2. 递归处理左子树
  3. 递归处理右子树

递归三要素：

1. 递归终止条件（通常处理空节点）
2. 当前层处理逻辑
3. 递归调用子问题

3. 树的特殊性质应用

• 二叉树：每个节点最多两个子节点
• 二叉搜索树(BST)：左子树所有值 < 根 < 右子树所有值
• 平衡二叉树：左右子树高度差≤1（如AVL树、红黑树）

三、分析解决树问题的步骤

1. 明确问题类型

• 遍历问题：路径查找、节点统计
• 结构问题：树的重建、镜像、平衡判断
• 属性问题：最大/小深度、直径、对称性
• 搜索问题：BST查找、最近公共祖先
• 修改问题：插入、删除、旋转操作

2. 选择合适遍历方式

问题类型	推荐遍历方式	示例问题
路径相关	DFS（前/后序）	路径总和、最大路径和
按层处理	BFS（层序）	锯齿形遍历、层平均值
BST属性相关	中序遍历	验证BST、BST转有序链表
子树属性	后序遍历	子树和、树的高度

3. 设计递归方案

递归模板：

ReturnType traversal(TreeNode root) {
    // 1. 终止条件
    if (root == null) return baseValue;
    
    // 2. 递归调用子问题
    ReturnType left = traversal(root.left);
    ReturnType right = traversal(root.right);
    
    // 3. 当前层处理
    ReturnType result = process(root, left, right);
    
    return result;
}

4. 考虑边界条件

• 空树处理（root == null）
• 单节点树
• 只有左/右子树的树（斜树）
• 大深度树（防止栈溢出）

5. 复杂度优化

• 空间优化：使用Morris遍历实现O(1)空间复杂度
• 时间优化：记忆化递归、剪枝操作
• 尾递归优化：部分编译器支持（Java有限支持）

四、典型问题解决示例

示例1：二叉树的最大深度

问题：求二叉树的最大深度（最长路径节点数）

解决思路：

1. 使用后序遍历（自底向上）
2. 当前节点深度 = max(左子树深度, 右子树深度) + 1

Java实现：

public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    int left = maxDepth(root.left);
    int right = maxDepth(root.right);
    return Math.max(left, right) + 1;
}

复杂度：O(n)时间，O(h)空间（h为树高）

示例2：验证二叉搜索树

问题：判断二叉树是否为有效的BST

解决思路：

1. 使用中序遍历（BST应有序）
2. 记录前驱节点，确保当前节点 > 前驱节点

Java实现：

TreeNode prev = null;

public boolean isValidBST(TreeNode root) {
    if (root == null) return true;
    
    // 检查左子树
    if (!isValidBST(root.left)) return false;
    
    // 检查当前节点
    if (prev != null && root.val <= prev.val) return false;
    prev = root;
    
    // 检查右子树
    return isValidBST(root.right);
}

五、JDK8+新特性应用

1. Stream API在树遍历中的应用

// 层序遍历收集所有节点值
List<Integer> values = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);

while (!queue.isEmpty()) {
    TreeNode node = queue.poll();
    values.add(node.val);
    if (node.left != null) queue.offer(node.left);
    if (node.right != null) queue.offer(node.right);
}

// 使用Stream处理结果
long count = values.stream().filter(v -> v > 10).count();
List<Integer> sorted = values.stream().sorted().toList();

2. Optional避免空指针

public int safeGetDepth(TreeNode root) {
    return Optional.ofNullable(root)
        .map(node -> 1 + Math.max(safeGetDepth(node.left), safeGetDepth(node.right)))
        .orElse(0);
}

六、重要注意事项

1. 递归深度限制：Java默认栈大小约1024KB，深度过大时考虑迭代解法
2. 树结构修改：在遍历中修改结构可能导致意外结果（如删除节点）
3. BST边界处理：使用Long.MIN_VALUE/MAX_VALUE避免Integer边界问题
4. 线程安全：多线程环境下考虑ConcurrentLinkedQueue等并发集合
5. 对象引用：递归中传递可变对象时注意引用共享问题

七、总结

解决树问题的核心方法论：

1. 识别类型：明确是遍历、搜索还是结构问题
2. 选择遍历：根据问题特性选择DFS（前/中/后序）或BFS（层序）
3. 递归设计：遵循"终止条件-递归调用-当前处理"模式
4. 边界处理：特别注意空树、单子树等边界情况
5. 优化考量：对大深度树使用迭代，对BST利用有序特性

掌握这些基础后，可通过LeetCode等平台专项练习：

• 基础：104(最大深度), 110(平衡树)
• 进阶：124(最大路径和), 297(序列化)
• BST：98(验证), 235(最近公共祖先)

"树是递归定义的，树问题也最好用递归解决。" - 计算机科学格言