Luobuyu's Blog

0%

124.二叉树中的最大路径和

发表于 分类于 ， ， 热度： ℃ 评论：
本文字数： 841 阅读时长 ≈ 1 分钟
使用树形dp，很容易。

124.二叉树中的最大路径和

题目描述：

二叉树节点权值为 $val$ ，返回得找到最大路径权值和。

数据范围：
$-10^3\le val \le 10^3;1\le 3\times10^4$

题解：

使用树形dp，对每个节点，维护所有子树路径的最大值，所有可能的路径为 $\max(left + right - val,val, left,right)$ ，取最大值更新答案。最后返回时，需要返回当前结点的最大值，注意不能包含该节点，所以为 $\max(left,right, val)$ .

其实可以直接在子树返回值处和 $0$ 取最大值。如果取到 $0$ 说明不包含该子树。

1
2
3
4
int left = max(dfs(root->left), 0);
int right = max(dfs(root->right), 0);
ans = max(ans, left + right + root->val);
return max(left, right) + root->val;

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int ans = -1e9;
    int dfs(TreeNode* root)
    {
        if(root == nullptr) return 0;
        int all = -1e9;
        int left = dfs(root->left) + root->val;
        int right = dfs(root->right) + root->val;
        all = left + right - root->val;
        ans = max(ans, root->val);
        ans = max(ans, all);
        ans = max(ans, max(left, right));
        return max(root->val, max(left, right));
    }
    int maxPathSum(TreeNode* root) {
        dfs(root);
        return ans;
    }
};