掌握树分治算法（Python实现树形分治与递归技巧详解）

为什么使用树分治？

当你面对如下问题时，树分治可能是最佳选择：

• 求树的最大路径和
• 统计满足某种条件的子树数量
• 求树的直径
• 分配资源使得子树满足约束

这些问题的共同点是：每个子树的结果可以独立计算，并用于构建父节点的答案。这正是递归算法和分治思想的用武之地。

实战：用Python实现树的最大路径和

我们以“二叉树中的最大路径和”为例（LeetCode 第124题），演示如何用Python树分治算法解决实际问题。

问题描述：给定一个非空二叉树，找到路径和最大的路径。路径被定义为从某一节点出发，沿父-子连接到达任意节点的序列。

class TreeNode:    def __init__(self, val=0, left=None, right=None):        self.val = val        self.left = left        self.right = rightglobal_max = float('-inf')def max_gain(node):    """    返回以当前节点为起点，向下延伸的最大路径和    同时更新全局最大路径和    """    global global_max        if not node:        return 0        # 递归计算左右子树的最大贡献值    left_gain = max(max_gain(node.left), 0)    right_gain = max(max_gain(node.right), 0)        # 当前节点作为路径最高点的路径和    price_newpath = node.val + left_gain + right_gain        # 更新全局最大值    global_max = max(global_max, price_newpath)        # 返回当前节点向上传递的最大贡献值    return node.val + max(left_gain, right_gain)def max_path_sum(root):    global global_max    global_max = float('-inf')    max_gain(root)    return global_max# 示例使用# 构建树:     -10#            /   \#           9    20#               /  \#              15   7root = TreeNode(-10)root.left = TreeNode(9)root.right = TreeNode(20)root.right.left = TreeNode(15)root.right.right = TreeNode(7)print(max_path_sum(root))  # 输出: 42 (15 + 20 + 7)

代码解析

这段代码完美体现了树形DP的思想：

1. 递归分解：对每个节点，先递归处理左右子树。
2. 子问题求解：计算左右子树能提供的最大“增益”（即路径和，若为负则舍弃）。
3. 合并结果：以当前节点为顶点的路径和 = 节点值 + 左增益 + 右增益。
4. 向上返回：只返回单侧最大增益（因为路径不能分叉），供父节点使用。

小贴士：避免常见错误

• 不要忘记处理负数：负贡献应舍弃（用 max(..., 0)）。
• 全局变量要小心：多测试用例时记得重置（如 global_max）。
• 理解“路径”定义：不能重复访问节点，因此向上只能传一侧结果。

总结

通过本教程，你已经掌握了Python树分治算法的基本框架。关键在于：将树问题拆解为子树问题，用递归算法自底向上求解，并在回溯过程中合并答案。这种分治思想不仅适用于路径和问题，还可扩展到各种树形DP场景。

动手尝试修改上述代码，解决“树的直径”或“最大平均值子树”等问题，你会对树分治有更深的理解！