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

二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

示例 1：

输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

示例 2：

输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

提示：

• 树中节点数目范围是 [1, 3 * 104]
• -1000 <= Node.val <= 1000

 

 int four(int a,int b,int c)

    {

        int tmp =a>b?a:b;

        tmp =tmp>c?tmp:c;

        return tmp;

    }

    int retMax=-10000;

    int  back(TreeNode* root)

    {

        if(root==nullptr)

        {

            return 0;

        }

        int left = back(root->left);

        int right = back(root->right);

        int rootSum = left+right+root->val;

        int tmp = root->val>rootSum?root->val:rootSum;

        if(tmp>retMax)

        {

            retMax=tmp;

        }

        int leftSum =root->val+left;

        int rightSum =root->val+right;

        tmp = four(root->val,leftSum,rightSum);

        if(tmp>retMax)

        {

            retMax=tmp;

        }

        return tmp;

    }

 

    int maxPathSum(TreeNode* root) {

        back(root);

        return retMax;

    }