递归返回向下最大贡献 max(0,child)，经过点的两侧贡献更新全局答案。
OJ: leetcodecn
题目 ID: binary-tree-maximum-path-sum
难度:提高+/省选-
标签:二叉树树形DP递归cpppython
日期: 2026-07-29 13:10
题意
路径可以从任意节点开始到任意节点结束，求路径和最大值。
思路
后序返回"以该节点为端点的向下最大单侧和"（负数视为 0），经过当前节点的候选为 left + right + val，全局更新。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
int maxPathSum(TreeNode *root) {
int ans = INT_MIN;
function<int(TreeNode *)> dfs = [&](TreeNode *r) {
if (!r)
return 0;
// 负贡献不选；左右贡献可与当前节点组成一条完整路径。
int l = max(0, dfs(r->left)), rd = max(0, dfs(r->right));
ans = max(ans, l + rd + r->val);
// 返回给父节点的路径只能选择左、右中的一侧。
return max(l, rd) + r->val;
};
dfs(root);
return ans;
}
};
TreeNode *build(istream &in, int n) {
vector<TreeNode *> nodes(n);
queue<TreeNode *> q;
for (int i = 0, v; i < n; i++) {
in >> v;
if (v != -1)
nodes[i] = new TreeNode(v);
}
TreeNode *root = nodes[0];
if (root)
q.push(root);
int idx = 1;
while (!q.empty() && idx < n) {
auto cur = q.front();
q.pop();
if (idx < n) {
cur->left = nodes[idx];
if (nodes[idx])
q.push(nodes[idx]);
idx++;
}
if (idx < n) {
cur->right = nodes[idx];
if (nodes[idx])
q.push(nodes[idx]);
idx++;
}
}
return root;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
auto r = build(cin, n);
cout << Solution().maxPathSum(r) << '\n';
return 0;
}python
#!/usr/bin/env python3
from collections import deque
from typing import Optional
class TreeNode:
def __init__(self, x):
self.val = x
self.left = self.right = None
class Solution:
def maxPathSum(self, root: Optional[TreeNode]) -> int:
ans = float("-inf")
def dfs(r):
nonlocal ans
if not r:
return 0
l = max(0, dfs(r.left))
rd = max(0, dfs(r.right))
ans = max(ans, l + rd + r.val)
return max(l, rd) + r.val
dfs(root)
return ans
def build(arr):
if not arr:
return None
nodes = [TreeNode(v) if v != -1 else None for v in arr]
q = deque([nodes[0]]) if nodes[0] else deque()
idx = 1
while q and idx < len(arr):
cur = q.popleft()
if idx < len(arr):
cur.left = nodes[idx]
if nodes[idx]:
q.append(nodes[idx])
idx += 1
if idx < len(arr):
cur.right = nodes[idx]
if nodes[idx]:
q.append(nodes[idx])
idx += 1
return nodes[0]
def main():
n = int(input())
a = list(map(int, input().split()))
print(Solution().maxPathSum(build(a)))
if __name__ == "__main__":
main()复杂度
时间 O(n)，空间 O(height)。
总结
与直径问题统一为"后序返回单侧、全局更新跨点答案"的树形 DP 模式。