Binary Tree Maximum Path Sum

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

分析

递归定义：
- 对于每个节点，我们通过递归计算以该节点为根的路径的最大贡献值（即该节点能为父节点提供的最大路径和）
贡献值的计算：
- 对于当前节点 root ：
  - 左子树提供的最大路径和 left = max(0, dfs(root->left))。取 0 是为了避免负贡献
  - 右子树提供的最大路径和 right = max(0, dfs(root->right))
更新全局最大路径和：
- 对于当前节点，路径和可能包含其左右子树的贡献值，因此计算路径和为：left + root->val + right
- 更新全局变量 res：res = max(res, left + root->val + right)
返回贡献值：
- 当前节点对父节点的最大贡献值为：root->val + max(left, right)，只取左右子树中的一个路径，避免形成环

时间复杂度

总时间复杂度 O(n)

空间复杂度

空间复杂度为 O(h)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


class Solution
{
public:
    int res = INT_MIN; // 全局变量，用于记录最大路径和

    int maxPathSum(TreeNode* root)
    {
        dfs(root); // 调用递归函数
        return res; // 返回最终结果
    }

    int dfs(TreeNode* root)
    {
        if (!root) // 如果当前节点为空，返回0
            return 0;

        // 递归计算左、右子树的最大贡献值，负值取0
        int left = std::max(0, dfs(root->left));
        int right = std::max(0, dfs(root->right));

        // 更新全局最大路径和
        res = std::max(res, left + root->val + right);

        // 返回当前节点对父节点的最大贡献值
        return root->val + std::max(left, right);
    }
};