题目描述

image.png

题解

使用递归算法，思路是将“求解包含每个节点的最大路径和”作为一个递归单元，可能有四种情况：

• 该节点加上其左子树的最大路径和
• 该节点加上其右子树的最大路径和
• 左右子树的路径加上该节点（相当于横跨该节点的路径）
• 该节点本身

设置一个全局最大量，求解包含每个节点的最大路径和，然后更新全局最大量
同时每个节点还需要向上层传递一个最大值，但第三种情况是不能向上层传递的（否则就会出现分叉，而不是一条路径）

这里还要利用“最大连续子序列和”问题中的思想，遇到小于0的值时，加上该值一定更小。所以当左子树返回的值小于0时，包含当前节点的最大路径和不可能与左子树连接，右子树同理。
利用这一思想，左子树或右子树返回的值先与0作比较，可以节省一些逻辑判断

补充知识：
C++库中表示整形最小值的宏：

INT_MIN

C++库中求两个数中更大值的函数：

max(a, b)

代码

// maxPathSum.cpp
#include <iostream>
using namespace std;

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


class Solution {
public:
    /**
     *
     * @param root TreeNode类
     * @return int整形
     */
    int maxPathSum(TreeNode* root) {
        // write code here
        maxSumNum = INT_MIN;
        maxSum(root);
        return maxSumNum;

    }
private:
    int maxSumNum = 0;
    int maxSum(TreeNode* t){

        if (t == NULL){
            return 0;
        }

        int maxLeft = max(0, maxSum(t->left));

        int maxRight = max(0, maxSum(t->right));

        maxSumNum = max(maxSumNum, maxLeft + t->val + maxRight);

        return max(maxLeft, maxRight) + t->val;

    }
};

int main(){
    TreeNode* root = new TreeNode;
    root->val = 1;
    root->left = new TreeNode;
    root->left->val = 2;
    root->left->left = NULL;
    root->left->right = NULL;
    root->right = new TreeNode;
    root->right->left = NULL;
    root->right->right = NULL;
    root->right->val = 3;
    Solution s;
    cout << s.maxPathSum(root) << endl;

    delete root->left;
    delete root->right;
    delete root;
    return 0;
}