题目链接

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

题解

• 递归解法
• 路径：一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
• 这道题和LeetCode687最长同值路径和LeetCode543二叉树的直径很相似，都很难，每个题都做了很久
  • 这道题和LeetCode687是很像的，差异不大；和LeetCode543还是有些差异的。
• 思路见代码注释
• 需要高度注意dfs函数的功能

// Problem: LeetCode 124
// URL: https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/
// Tags: Tree Recursion DFS
// Difficulty: Hard

#include <iostream>
#include <algorithm>
using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
};

class Solution
{
private:
    int maxSum = INT_MIN; // 全局最大路径和

    // 功能：求一颗树的最大路径和，要求从根节点开始，在左子树或右子树结束，也可不经过左子树和右子树，即至多经过一个子树
    int dfs(TreeNode *root)
    {
        if (root == nullptr)
            return 0;
        int left = dfs(root->left);
        int right = dfs(root->right);
        // 过程中更新全局最大路径和：根节点必须经过，左右子树可经过可不经过
        maxSum = max(maxSum, root->val + max(left, 0) + max(right, 0));
        // 从根节点开始，在左子树或右子树结束，也可不经过左子树和右子树，即至多经过一个子树
        return max(root->val, root->val + max(max(left, right), 0));
    }

public:
    // 求一颗树的最大路径和，不要求经过根节点，起始和终止节点任意
    int maxPathSum(TreeNode *root)
    {
        dfs(root);
        return this->maxSum;
    }
};

作者：@臭咸鱼

转载请注明出处：https://www.cnblogs.com/chouxianyu/

欢迎讨论和交流!

原文：https://www.cnblogs.com/chouxianyu/p/13386394.html