Binary Tree Maximum Path Sum.png
解題思路 ：
此題反而比 II 還要多一個考慮的點 如果 left + right + root->val 本身的值就已經是最大值 必須要把此值保留 特別注意 findMax function 回傳的並不是 res 而是 node 本身的值 加上左邊或右邊二選一 ( 選最大者 因為一次只能走一條路訪問一個子節點 )
C++ code :
<pre><code>
/**
- Definition of TreeNode:
- class TreeNode {
- public:
int val;TreeNode *left, *right;TreeNode(int val) {this->val = val;this->left = this->right = NULL;}- }
*/
class Solution {
public:
/**
* @param root: The root of binary tree.
* @return: An integer
*/
// write your code here
int findMax(TreeNode *root, int &res)
{
if(root == nullptr) return 0;
int sum = root->val;
int left = findMax(root->left, res);
int right = findMax(root->right, res);
if(left > 0) sum += left;
if(right > 0) sum += right;
res = max(res, sum);
return max(max(left, right) + root->val, root->val);
}
int maxPathSum(TreeNode *root) {
int res = INT_MIN;
findMax(root, res);
return res;
}
};
