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 { private: int solution(TreeNode* root, int& best){ // my own solution if (!root) return 0; int left_sum = root->val + solution(root->left, best); int right_sum = root->val + solution(root->right, best); int curve_sum = left_sum + right_sum - root->val; best = max({best, left_sum, right_sum, curve_sum, root->val}); return max({left_sum, right_sum, root -> val}); } public: int maxPathSum(TreeNode* root) { // it is the original function int best = INT_MIN; int eval = solution(root, best); return max(best, eval); } };
【hard】124. Binary Tree Maximum Path Sum
原文：https://www.cnblogs.com/sherry-yang/p/11421704.html