124. 二叉树中的最大路径和
3 min
题目
解法：DFS
思路
核心思想是后序遍历+动态规划，对每个节点计算其作为路径最高点的最大和，以及能向父节点提供的最大单边贡献。
正确性基于：任何路径要么以某节点为最高点（可包含左右子树），要么从某节点向上延伸（只能选择左或右子树之一）。通过 max(0, 子树贡献) 忽略负贡献，确保最优性。自底向上的递归保证每个节点的计算都基于子树的最优解。
- Step 1: 递归计算左子树最大贡献，若为负则取0
- Step 2: 递归计算右子树最大贡献，若为负则取0
- Step 3: 更新全局答案 ans = max(ans, 当前节点值 + 左贡献 + 右贡献)
- Step 4: 返回给父节点的值为 当前节点值 + max(左贡献, 右贡献)
复杂度
- 时间复杂度:
- 空间复杂度: ，其中 h 为树的高度，递归栈空间
代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
int ans = INT_MIN;
int dfs(TreeNode* root) {
if (root == nullptr) return 0;
int left = max(0, dfs(root->left)); // 左子树最大贡献
int right = max(0, dfs(root->right)); // 右子树最大贡献
// 当前节点作为路径最高点
ans = max(ans, root->val + left + right);
// 返回给父节点的最大单边贡献
return root->val + max(left, right);
}
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
int ans = INT_MIN;
int dfs(TreeNode* root) {
if (root == nullptr) return 0;
int left = max(0, dfs(root->left)); // 左子树最大贡献
int right = max(0, dfs(root->right)); // 右子树最大贡献
// 当前节点作为路径最高点
ans = max(ans, root->val + left + right);
// 返回给父节点的最大单边贡献
return root->val + max(left, right);
}
int maxPathSum(TreeNode* root) {
dfs(root);
return ans;
}
};