1

## 資結經典題目: 在二元樹中找最長路徑和

``````input:
-10
/ \
9  20
/  \
15   7
output: 42 (15-20-7有最大路徑和42)
``````

Note: 本題樹結構的定義為

``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
``````

# 解法一、有點暴力的解，耗時1292ms

1. `int maxSinglePathPassRoot(TreeNode* root)`: 計算通過root的單向路徑最大總和(只能往左邊或往右邊走)，如果root為空則只好回傳0，否則至少要包含root的值
2. `int maxPathPassRoot(TreeNode* root)`: 計算通過root的路徑最大總和，把左右兩邊最大路徑加總就是了

``````class Solution {
public:
int maxSinglePathPassRoot(TreeNode* root){
if(root==NULL){
return 0;
}
int left = max(0,maxSinglePathPassRoot(root->left));
int right = max(0,maxSinglePathPassRoot(root->right));
return root->val+max(left, right);

}

int maxPathPassRoot(TreeNode* root){
if(root==NULL){
return 0;
}
int left = max(0,maxSinglePathPassRoot(root->left));
int right = max(0,maxSinglePathPassRoot(root->right));
return root->val+left+right;
}

int maxPathSum(TreeNode* root) {
int M = maxPathPassRoot(root);
if(root->left){
M = max(M, maxPathSum(root->left));
}
if(root->right){
M = max(M, maxPathSum(root->right));
}
return M;
}
};
``````

# 解法二、改良版，呼叫 maxSinglePathPassRoot時即更新最大值，耗時40ms

``````class Solution {
public:
int maxSinglePathPassRoot(TreeNode* root, int &MAX){
if(root==NULL){
return 0;
}
int left = max(0,maxSinglePathPassRoot(root->left, MAX));
int right = max(0,maxSinglePathPassRoot(root->right, MAX));
MAX = max(MAX, root->val + left+ right);
return root->val+max(left, right);
}

int maxPathSum(TreeNode* root) {
int M = root->val;
maxSinglePathPassRoot(root, M);
return M;
}
};
``````

# 補充- LeetCode- 543. Diameter of Binary Tree

``````class Solution {
public:
int maxSinglePathPassRoot(TreeNode* root, int &MAX){
if(root==NULL){
return 0;
}
int left = max(0,maxSinglePathPassRoot(root->left, MAX));
int right = max(0,maxSinglePathPassRoot(root->right, MAX));
MAX = max(MAX, 1 + left+ right);
return 1+max(left, right);
}

int diameterOfBinaryTree(TreeNode* root) {
if(root==NULL){
return 0;
}
int M = 0;
maxSinglePathPassRoot(root, M);
return M-1;
}
};
``````