二叉树中的最大路径和

怎样从“任意非空路径最大和,例 [-10,9,20,null,null,15,7] 答案 42。”推导出 二叉树 · 最大路径，并证明每次状态变化都不会漏掉答案？

中心结论：后序:leftGain=max(0,dfs(L));global=max(global,val+L+R);return val+max(L,R)。

给定一个非空二叉树，返回其最大路径和。本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

在本站主例中，任意非空路径最大和,例 [-10,9,20,null,null,15,7] 答案 42。

算法最终需要得到或观察：最大路径和 42,路径 15→20→7 不过 root。

从每个节点重新遍历子树会重复计算；递归让每棵子树只计算一次并向父节点返回摘要。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“递归回执树”，明确答案需要观察什么。
2. 2状态只维护 leftGain/rightGain/global/return 双语义。
3. 3转移每一步按照 后序:leftGain=max(0,dfs(L));global=max(global,val+L+R);return val+max(L,R)。
4. 4收尾读取 最大路径和 42,路径 15→20→7 不过 root。，并复核边界与复杂度。

先用一句话定义递归函数返回什么，父节点才能正确合并。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：leftGain/rightGain/global/return 双语义。

给出一个二叉树，要求找一条路径使得路径的和是最大的。 这一题思路比较简单，递归维护最大值即可。不过需要比较的对象比较多。`maxPathSum(root) = max(maxPathSum(root.Left), maxPathSum(root.Right), maxPathSumFrom(root.Left) (if>0) + maxPathSumFrom(root.Right) (if>0) + root.Val)` ，其中，`maxPathSumFrom(root) = max(maxPathSumFrom(root.Left), maxPathSumFrom(root.Right)) + root.Val`

后序:leftGain=max(0,dfs(L));global=max(global,val+L+R);return val+max(L,R)。

执行过程中持续维护：leftGain/rightGain/global/return 双语义。

正确性依赖以下不变量：global 拐点可接左右;return 给父节点只能报单边链。

面试时可以压缩为：后序 DFS,max(0,gain)剪负贡献,global更新拐点,return单边,O(n)时间O(h)空间。

落到当前题，执行机制可以压缩为：后序:leftGain=max(0,dfs(L));global=max(global,val+L+R);return val+max(L,R)。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入任意非空路径最大和,例 [-10,9,20,null,null,15,7] 答案 42。 因为：后序:leftGain=max(0,dfs(L));global=max(global,val+L+R);return val+max(L,R)。
2. 2DFS 维护剩余和每步减去当前结点值。 因为：叶子处 remain 应为 0。
3. 3叶子 9,remain=23,不命中检查是否等于 target。 因为：只有根到叶路径才计数。
4. 4预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
5. 5经过 20,remain → 12继续向下。 因为：只有根到叶路径才计数。
6. 6叶子 15,remain=-3,不命中检查是否等于 target。 因为：只有根到叶路径才计数。
7. 7不存在全部路径检查完。 因为：O(n) DFS。
8. 8收尾与复杂度最大路径和 42,路径 15→20→7 不过 root。 因为：时间 O(n) · 空间 O(h)。后序:leftGain=max(0,dfs(L));global=max(global,val+L+R);return val+max(L,R)。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

import (
	"math"

)

// TreeNode define
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func maxPathSum(root *TreeNode) int {
	if root == nil {
		return 0
	}
	max := math.MinInt32
	getPathSum(root, &max)
	return max
}

func getPathSum(root *TreeNode, maxSum *int) int {
	if root == nil {
		return math.MinInt32
	}
	left := getPathSum(root.Left, maxSum)
	right := getPathSum(root.Right, maxSum)

	currMax := max(max(left+root.Val, right+root.Val), root.Val)
	*maxSum = max(*maxSum, max(currMax, left+right+root.Val))
	return currMax
}

func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
    // 1. 主例
    //    输入：mode="path-sum", values=[-10,9,20,null,null,15,7]
    //    期望：最大路径和 42,路径 15→20→7 不过 root。
    //
    // 2. 失败 / 未命中
    //    检查：global 与 return 语义不同;勿用 LC112 root→leaf 模型。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC543 直径；LC687 最长 Univalue
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意任意非空路径最大和,例 [-10,9,20,null,null,15,7] 答案 42。
2. 2重复从每个节点重新遍历子树会重复计算；递归让每棵子树只计算一次并向父节点返回摘要。
3. 3优化后序:leftGain=max(0,dfs(L));global=max(global,val+L+R);return val+max(L,R)。
4. 4证明global 拐点可接左右;return 给父节点只能报单边链。
5. 5复杂度时间 O(n)，空间 O(h)