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.

题解：

　　感觉解题思路有点类似于动态规划，一个变量用于表示以此节点为根的最大路径和，另一个变量为全局变量，全局更新最大值

1 class Solution { 2 public: 3     int maxPathSum(TreeNode* root) { 4         if (!root) 5             return 0; 6         int res = INT_MIN; 7         helper(root, res); 8         return res; 9     }10     11     int helper(TreeNode* root, int& res) {12         if (!root)13             return 0;14         15         int lmax = max(helper(root->left, res), 0);16         int rmax = max(helper(root->right, res), 0);17         res = max(lmax + rmax + root->val, res);18         return max(lmax, rmax) + root->val;19     }20 };