LeetCode124 二叉树中的最大路径和

发表于 | 分类于 |
字数统计: 204 | 阅读时长 ≈ 1

链接: https://leetcode.cn/problems/binary-tree-maximum-path-sum/

题意

路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列
给你一个二叉树的根节点 root ，返回其最大路径和。

解法

递归处理问题
对于每个节点，其作为路径的候选值是左节点部分的值加上当前节点加上右节点部分
并更新最大的值
然后返回左节点或是右节点加上当前节点的值

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxv;
    int dfs(TreeNode* root) {
        if (!root) return 0;
        int l = max(0, dfs(root -> left)), r = max(0, dfs(root -> right));
        maxv = max(maxv, root -> val + l + r);
        return max(l, r) + root -> val;
    }

    int maxPathSum(TreeNode* root) {
        maxv = root -> val;
        int ret = dfs(root);
        return maxv;
    }
};