偶然在面试题里面看到这个题所以就在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 = -9999999;     int maxPathSum(TreeNode* root) {        maxpath(root);        return MAX;    }    int maxpath(TreeNode *node){        if(node == NULL)            return 0;        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;        }    }    };