1
      /      2   3

Discuss

#include <iostream>
#include <vector>
#include <climits>
using std::vector;


/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/


struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};


class Solution
{
private:
    int maxPathSum(TreeNode *root, int &Result)
    {
        if (!root)
        {
            return 0;
        }

        int RootResult = root->val;

        int LeftResult = maxPathSum(root->left, Result);
        int RightResult = maxPathSum(root->right, Result);

        LeftResult = LeftResult * (LeftResult > 0);
        RightResult = RightResult * (RightResult > 0);

        // all the tree
        int TmpResult = RootResult + LeftResult + RightResult;

        if (Result < TmpResult)
        {
            Result = TmpResult;
        }

        // only left subtree or the right subtree
        TmpResult = RootResult + (LeftResult > RightResult? LeftResult : RightResult);

        if (Result < TmpResult)
        {
            Result = TmpResult;
        }

        return TmpResult;
    }

public:
    int maxPathSum(TreeNode* root)
    {
        int Result = INT_MIN;
        maxPathSum(root, Result);

        return Result;
    }
};

版权声明：本文为博主原创文章，未经博主允许不得转载。