偶然在面试题里面看到这个题所以就在Leetcode上找了一下，不过Leetcode上的比较简单一点。

题目：

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

For example:
Given the below binary tree,

       1

      / \

     2   3

Return 6.

暴力解法就是将每一个节点作为开始节点，寻找最大的路径长度，感觉和在一个整数序列中寻找和最大的子序列差不多，不同的是每一个开始节点有几条不同的路。再仔细想一想就知道，每一条路径肯定都有一个最高的节点，把每一个节点作为一条路径的最高节点并且是这个路径的末端节点，可以应用递归来解决这个问题。假设节点x为这条路径的最高节点和末端节点，求得这条路径的函数为maxpath（x）=max(maxpath(x->left)+x->val, maxpath(x->right)+x->val, x->val) 。调用根节点的maxpath可以计算出以每个节点为最高节点和末端节点的路径的最大值，那以该节点为最高节点的路径的最大值为maxpath（x）或者maxpath(x->left)+maxpath(x->right)+x->val，可以用MAX记录这个值，最后函数返回MAX

/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

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

 * };

 */

class Solution {

public:

    int MAX = -;

    int maxPathSum(TreeNode* root) {

        maxpath(root);

        return MAX;

    }

    int maxpath(TreeNode *node){

        if(node == NULL)

            return ;

        else{

            int x = maxpath(node->left), y = maxpath(node->right);

            int maxlen = x+node->val > node->val? x+node->val:node->val;

            int result = maxlen > y+node->val?maxlen:y+node->val;

            MAX = result>MAX?result:MAX;

            MAX = x+y+node->val>MAX? x+y+node->val:MAX;

            return result;

        }

    }

};