124. Binary Tree Maximum Path Sum（难）

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 does not need to go through the root.

For example:
Given the below binary tree,

1 / \ 2 3

​​6​​.

编程之美: 求二叉树中节点的最大距离 很像

/**
 * 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 maxPathSum(TreeNode* root) {
     if (root == NULL) return 0;
     maxSum = INT_MIN;
     maxPathDown(root);
     return maxSum;
   }

 private:
   int maxPathDown(TreeNode* root){
     if (root == NULL) return 0;
     int left = max(0,maxPathDown(root->left));
     int right =max(0, maxPathDown(root->right));
     
     maxSum = max(maxSum, left + right + root->val);

     return max(left, right) + root->val;
   }
   int maxSum;
 };