1. 题目解析与核心思路LeetCode 124题二叉树中的最大路径和是一个经典的树形动态规划问题。题目要求我们在一棵二叉树中寻找一条路径使得路径上所有节点值的和最大。这里的路径定义为任意节点序列序列中每对相邻节点之间都存在一条边且同一个节点在路径序列中至多出现一次。1.1 问题重述给定一棵二叉树的根节点root返回其最大路径和。路径不需要从根节点开始也不需要在叶子节点结束但必须保证路径是连续的。例如输入root [-10,9,20,null,null,15,7] 输出42 解释最优路径是15 → 20 → 7路径和为15207421.2 关键观察点解决这个问题的关键在于理解路径的构成方式。对于任意一个节点经过它的最大路径和可能有以下三种情况只包含该节点本身该节点加上左子树的某条路径该节点加上右子树的某条路径该节点加上左右子树的路径形成拐弯路径2. 树形DP解法详解2.1 递归定义我们定义一个递归函数maxGain(node)它返回以node为起点的向下延伸的最大路径和即不拐弯。同时在递归过程中我们会计算经过node的最大路径和可能拐弯并更新全局最大值。class Solution { public: int maxPathSum(TreeNode* root) { int maxSum INT_MIN; maxGain(root, maxSum); return maxSum; } private: int maxGain(TreeNode* node, int maxSum) { if (!node) return 0; // 递归计算左右子树的最大贡献值 int leftGain max(maxGain(node-left, maxSum), 0); int rightGain max(maxGain(node-right, maxSum), 0); // 计算经过当前节点的最大路径和可能拐弯 int priceNewPath node-val leftGain rightGain; // 更新全局最大值 maxSum max(maxSum, priceNewPath); // 返回当前节点的最大贡献值不拐弯 return node-val max(leftGain, rightGain); } };2.2 时间复杂度分析这个解法采用后序遍历的方式访问每个节点恰好一次因此时间复杂度是O(N)其中N是二叉树中的节点数量。空间复杂度取决于递归栈的深度最坏情况下树退化为链表为O(N)。3. 实现细节与边界处理3.1 初始值设置全局最大值maxSum初始化为INT_MIN这样可以正确处理所有节点值都为负数的情况。例如树中所有节点都是-1那么最大路径和应该是-1单个节点。3.2 负贡献处理在计算左右子树的贡献时我们使用max(..., 0)来忽略负贡献。这意味着如果某子树的贡献为负我们宁愿不选择它。3.3 空节点处理当节点为nullptr时maxGain返回0表示空子树没有贡献。4. 常见错误与调试技巧4.1 典型错误模式忘记处理负值情况导致计算结果偏大混淆了节点最大贡献值和经过该节点的最大路径和两个概念没有正确初始化全局最大值导致全负数情况出错4.2 调试建议对于树类问题建议构造以下测试用例单节点树全负数树完全二叉树退化为链表的树常规的平衡树例如void test() { Solution sol; // 单节点 TreeNode* t1 new TreeNode(5); assert(sol.maxPathSum(t1) 5); // 全负数 TreeNode* t2 new TreeNode(-3); t2-left new TreeNode(-5); t2-right new TreeNode(-1); assert(sol.maxPathSum(t2) -1); // 常规案例 TreeNode* t3 new TreeNode(-10); t3-left new TreeNode(9); t3-right new TreeNode(20); t3-right-left new TreeNode(15); t3-right-right new TreeNode(7); assert(sol.maxPathSum(t3) 42); }5. 算法优化与变种思考5.1 非递归实现虽然递归实现简洁但我们可以用后序迭代遍历来实现非递归版本。需要使用栈来模拟递归过程并额外维护每个节点的状态是否已处理左右子树。5.2 路径记录如果需要输出具体路径而不仅仅是和我们可以修改算法在递归过程中同时记录路径节点。这需要维护更多的状态信息但基本思路不变。5.3 多叉树扩展这个算法可以推广到多叉树情况。对于每个节点我们需要考虑所有子树的贡献选择最大的几个具体数量取决于路径定义来组合。6. 同类题目推荐LeetCode 543 - 二叉树的直径LeetCode 687 - 最长同值路径LeetCode 337 - 打家劫舍 IIILeetCode 1372 - 二叉树中的最长交错路径LeetCode 1026 - 节点与其祖先之间的最大差值这些题目都采用了类似的树形DP思路通过后序遍历在递归过程中维护和更新全局状态。掌握这个模式可以解决一大类二叉树路径问题。
1. 题目解析与核心思路LeetCode 124题二叉树中的最大路径和是一个经典的树形动态规划问题。题目要求我们在一棵二叉树中寻找一条路径使得路径上所有节点值的和最大。这里的路径定义为任意节点序列序列中每对相邻节点之间都存在一条边且同一个节点在路径序列中至多出现一次。1.1 问题重述给定一棵二叉树的根节点root返回其最大路径和。路径不需要从根节点开始也不需要在叶子节点结束但必须保证路径是连续的。例如输入root [-10,9,20,null,null,15,7] 输出42 解释最优路径是15 → 20 → 7路径和为15207421.2 关键观察点解决这个问题的关键在于理解路径的构成方式。对于任意一个节点经过它的最大路径和可能有以下三种情况只包含该节点本身该节点加上左子树的某条路径该节点加上右子树的某条路径该节点加上左右子树的路径形成拐弯路径2. 树形DP解法详解2.1 递归定义我们定义一个递归函数maxGain(node)它返回以node为起点的向下延伸的最大路径和即不拐弯。同时在递归过程中我们会计算经过node的最大路径和可能拐弯并更新全局最大值。class Solution { public: int maxPathSum(TreeNode* root) { int maxSum INT_MIN; maxGain(root, maxSum); return maxSum; } private: int maxGain(TreeNode* node, int maxSum) { if (!node) return 0; // 递归计算左右子树的最大贡献值 int leftGain max(maxGain(node-left, maxSum), 0); int rightGain max(maxGain(node-right, maxSum), 0); // 计算经过当前节点的最大路径和可能拐弯 int priceNewPath node-val leftGain rightGain; // 更新全局最大值 maxSum max(maxSum, priceNewPath); // 返回当前节点的最大贡献值不拐弯 return node-val max(leftGain, rightGain); } };2.2 时间复杂度分析这个解法采用后序遍历的方式访问每个节点恰好一次因此时间复杂度是O(N)其中N是二叉树中的节点数量。空间复杂度取决于递归栈的深度最坏情况下树退化为链表为O(N)。3. 实现细节与边界处理3.1 初始值设置全局最大值maxSum初始化为INT_MIN这样可以正确处理所有节点值都为负数的情况。例如树中所有节点都是-1那么最大路径和应该是-1单个节点。3.2 负贡献处理在计算左右子树的贡献时我们使用max(..., 0)来忽略负贡献。这意味着如果某子树的贡献为负我们宁愿不选择它。3.3 空节点处理当节点为nullptr时maxGain返回0表示空子树没有贡献。4. 常见错误与调试技巧4.1 典型错误模式忘记处理负值情况导致计算结果偏大混淆了节点最大贡献值和经过该节点的最大路径和两个概念没有正确初始化全局最大值导致全负数情况出错4.2 调试建议对于树类问题建议构造以下测试用例单节点树全负数树完全二叉树退化为链表的树常规的平衡树例如void test() { Solution sol; // 单节点 TreeNode* t1 new TreeNode(5); assert(sol.maxPathSum(t1) 5); // 全负数 TreeNode* t2 new TreeNode(-3); t2-left new TreeNode(-5); t2-right new TreeNode(-1); assert(sol.maxPathSum(t2) -1); // 常规案例 TreeNode* t3 new TreeNode(-10); t3-left new TreeNode(9); t3-right new TreeNode(20); t3-right-left new TreeNode(15); t3-right-right new TreeNode(7); assert(sol.maxPathSum(t3) 42); }5. 算法优化与变种思考5.1 非递归实现虽然递归实现简洁但我们可以用后序迭代遍历来实现非递归版本。需要使用栈来模拟递归过程并额外维护每个节点的状态是否已处理左右子树。5.2 路径记录如果需要输出具体路径而不仅仅是和我们可以修改算法在递归过程中同时记录路径节点。这需要维护更多的状态信息但基本思路不变。5.3 多叉树扩展这个算法可以推广到多叉树情况。对于每个节点我们需要考虑所有子树的贡献选择最大的几个具体数量取决于路径定义来组合。6. 同类题目推荐LeetCode 543 - 二叉树的直径LeetCode 687 - 最长同值路径LeetCode 337 - 打家劫舍 IIILeetCode 1372 - 二叉树中的最长交错路径LeetCode 1026 - 节点与其祖先之间的最大差值这些题目都采用了类似的树形DP思路通过后序遍历在递归过程中维护和更新全局状态。掌握这个模式可以解决一大类二叉树路径问题。
)
