LeetCode-124

问题复述

给一个二叉树的根节点root，求出从某一点出发得到的最大路径和。

解释一下：最大路径和中的路径可以是从某一双亲节点出发的路径，也可以是从某一叶子节点出发的路径。这就导致，如果从某一双亲节点出发，只能选择两个子节点中代价大的，也可能是从子节点出发，经过双亲节点的路径。所以程序中maxSum=max(maxSum,node->val+left+right)判断的是第二种情况，接着return max(left,right)+node->val这里是第一中情况，返回节点代价为上一层节点的判断提供依据。若上一层中 maxSum 比较出的值任然是原值，则表示第二种情况拥有最大路径和，而倘若 maxSum 更新了则表示下一层选择的路径是子节点中的一个。

理解递归的逻辑是关键，同时用框架的思维看，这一题就是后序遍历。

解决方案

利用递归，求出子节点的代价，再更新 maxSum 值，返回子节点选择出的最大代价路径的代价（只能选择左右中的一条，或者不选为0），递归返回到上一层。上一层判断是 max(left,right)+node->val 和 node->val+left+right 大小。

程序源码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
     int maxSum=INT_MIN;
public:
    int maxPathNode(TreeNode* node){
        if(node==nullptr)
            return 0;
        int left=max(0,maxPathNode(node->left));    //节点值大于零才被选入
        int right=max(0,maxPathNode(node->right));

        maxSum=max(maxSum,node->val+left+right);    //更新最大路径和

        return max(left,right)+node->val;   //相当于后序遍历
    }
    int maxPathSum(TreeNode* root) {
        maxPathNode(root);
        return maxSum;
    }
};