二叉树最大路径和问题要求在一棵二叉树中找到一条路径，使得路径上所有节点值之和最大。路径可以从任意节点开始、任意节点结束，但必须连续且不走回头路。解决该问题的关键是借助深度优先搜索，在递归过程中同时返回两个值：子树能提供的最大单边贡献，以及经过当前节点的最大路径和。
问题核心与双值返回思路
在每个节点上，路径有两种形态。一种是以该节点为最高点向下延伸的单边路径，用于向上层父节点提供贡献；另一种是以该节点为拐点，同时连接左右子树的路径，这是候选的全局最大路径。因此递归函数需要返回单边最大贡献，同时在函数内部用外部变量记录全局最大路径和。
递归函数的定义
设递归函数 dfs(node) 返回以 node 为起点向下走能得到的最大单边权和（至少包含 node 自身）。对于空节点返回 0。在计算时，若左右单边贡献为负，则不如不走该侧，因此与 0 取最大值。
单边贡献计算
- 左子树贡献：max(dfs(left), 0)
- 右子树贡献：max(dfs(right), 0)
- 当前单边返回：node.val + max(左贡献, 右贡献)
全局最大和更新
以当前节点为转折点的路径和为 node.val + 左贡献 + 右贡献，每次递归都用它尝试更新全局最大值。
代码实现示例
下面以 Python 为例展示完整解法。注意递归内部维护一个可变对象来保存答案。
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def maxPathSum(self, root):
# ans用来保存全局最大路径和
ans = [float('-inf')]
def dfs(node):
if node is None:
return 0
# 递归获取左右子树单边最大贡献，负数则取0
left_gain = max(dfs(node.left), 0)
right_gain = max(dfs(node.right), 0)
# 以当前节点为转折点的路径和
current_sum = node.val + left_gain + right_gain
# 更新全局最大值
if current_sum > ans[0]:
ans[0] = current_sum
# 返回当前节点向上的单边最大贡献
return node.val + max(left_gain, right_gain)
dfs(root)
return ans[0]
复杂度与注意事项
该算法对每个节点仅访问一次，时间复杂度为 O(n)，空间复杂度为递归栈的 O(h)，h 为树高。需要特别注意所有节点均为负数时，算法依靠与 0 取最大值以及初始负无穷设置，仍能正确返回唯一的单个最大负值节点。
双值返回策略的本质是把路径拆分：向上报单边，向内算转折，从而在一次深度优先搜索中完成全局最优求解。
小结
掌握二叉树最大路径和的关键在于理解递归返回值与全局变量的分工。深度优先搜索配合单边贡献与拐点路径的双值处理，能够清晰且高效地解决此类树形动态规划问题。