二叉树的题目虽然标着hard类型，但解起来有点爽，这道题目琢磨透了觉得非常的棒，可以说这种类型题目是一种套路。可以结合文章段错误segment fault分析一起使用更佳。或许屏幕前的朋友会有疑问，这篇讲函数调用栈的文章和leetcode124有啥关系?其实树里面很多递归的逻辑就是函数调用，直到调用到终止条件，然后层层向上返回的过程。

题目：

Given a non-empty 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.

Example 1:

Input: [1,2,3]

       1
      / \
     2   3

Output: 6
Example 2:

Input: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

Output: 42

解法：

/**
 * 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 {
    int maxPathSum(TreeNode *root, int &re) {
        if(NULL == root)
        {
            return 0;
        }
        
        int l = maxPathSum(root->left,re);
        int r = maxPathSum(root->right,re);
        
        l = (l < 0) ? 0 : l;
        r = (r < 0) ? 0 : r;
        
        if(l + r + root->val > re)
            re = l + r + root->val;
        
        return root->val += max(l, r);
    }
public:
    int maxPathSum(TreeNode* root) {
        int max = INT_MIN;
        maxPathSum(root, max);

        return max;
    }
};

配合如下输出，在leetcode中运行，结合输出结果理解更佳

/**
 * 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 {
    int maxPathSum(TreeNode *root, int &re) {
        if(NULL == root)
        {
            printf("call func maxPathSum,root NULL,re = %d.\n",re);
            return 0;
        }
        
        printf("call func maxPathSum,root->val:%d,re = %d.\n",root->val,re);
        int l = maxPathSum(root->left,re);
        int r = maxPathSum(root->right,re);
        
        l = (l < 0) ? 0 : l;
        r = (r < 0) ? 0 : r;
        
        if(l + r + root->val > re)
            re = l + r + root->val;
        
        int res = root->val + max(l, r);
        printf("return func l:%d,r:%d,val:%d,re:%d,res:%d\n",l,r,root->val,re,res);
        return res;
    }
public:
    int maxPathSum(TreeNode* root) {
        int max = INT_MIN;
        maxPathSum(root, max);

        return max;
    }
};

程序输出：

call func maxPathSum,root->val:-10,re = -2147483648.
call func maxPathSum,root->val:9,re = -2147483648.
call func maxPathSum,root NULL,re = -2147483648.
call func maxPathSum,root NULL,re = -2147483648.
return func l:0,r:0,val:9,re:9,res:9
call func maxPathSum,root->val:20,re = 9.
call func maxPathSum,root->val:15,re = 9.
call func maxPathSum,root NULL,re = 9.
call func maxPathSum,root NULL,re = 9.
return func l:0,r:0,val:15,re:15,res:15
call func maxPathSum,root->val:7,re = 15.
call func maxPathSum,root NULL,re = 15.
call func maxPathSum,root NULL,re = 15.
return func l:0,r:0,val:7,re:15,res:7
return func l:15,r:7,val:20,re:42,res:35
return func l:9,r:35,val:-10,re:42,res:25