Binary Tree Maximum Path Sum II

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

};