#include "stdafx.h"
#include <iostream>
#include <string>
#include <stdlib.h>
#include <vector>
#include <algorithm>
using namespace std;

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

class Solution {
public:
    int maxPathSum(TreeNode *root)
    {
        if (!root)
        {
            return 0;
        }
        int max_value = http://www.mamicode.com/-99999999;
        getMaxValue(root, max_value);
        return max_value;
    }
    int getMaxValue(TreeNode *root, int &max_value)
    {
        if (!root)
        {
            return 0;
        }
        int left = max(0, getMaxValue(root->left, max_value));
        int right = max(0, getMaxValue(root->right, max_value));
        max_value = max_value > root->val + left + right ? max_value : root->val + left + right;
        return (left > right ? left : right) + root->val;
    }
};
int main()
{
    TreeNode *tn1 = new TreeNode(3);
    TreeNode *tn2 = new TreeNode(4);
    TreeNode *tn3 = new TreeNode(5);
    TreeNode *tn4 = new TreeNode(6);
    TreeNode *tn5 = new TreeNode(7);
    TreeNode *tn6 = new TreeNode(8);
    tn1->left = tn2;
    tn1->right = tn3;
    tn2->left = tn4;
    tn2->right = tn5;
    tn3->right = tn6;
    Solution so;
    cout << so.maxPathSum(tn1) <<endl;
    return 0;
}