Binary Tree Maximum Path Sum.png
解題思路 ：
題目設計的路徑可以包涵 left + root + right 所以在記錄最大值的時候必須要比較 root->left(如果為正) 的最大值 + root + root->right(如果為正) 的最大值 但是要注意 node 的 traversal 一次只能走一條 所以在 function 中用 pass by reference 的方式改最大值的紀錄 但是 function 回傳值只能回傳左邊或右邊 ( 取大者 或是都不取如果兩邊走下去皆為負數 )
C++ code :
<pre><code>
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) 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;
}
};
