Binary Tree Maximum Path Sum II.png
解題思路 ：
另外建一個 function 來檢查 node 本身的 value 跟左右兩邊相加的結果 回傳最大者 有三項需要檢查:
1.root->val
2.root->val + left (left 是指左邊 child recursive 回傳的最大值)
3.root->val + right(right 是右邊 child recursive 回傳的最大值)
單純比較這三者 回傳最大者即可
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
*/
int findMax(TreeNode *root)
{
if(root == nullptr) return 0;
int left = findMax(root->left);
int right = findMax(root->right);
return max(max(left + root->val, root->val) , right + root->val );
}
int maxPathSum2(TreeNode *root) {
// Write your code here
int sum = 0;
if(root != nullptr) sum = findMax(root);
return sum;
}
};
