Binary Tree Maximum Path Sum

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;
}

};