Binary Tree Maximum Path Sum :
給定一個非空二叉樹，返回其最大路徑和
該路徑可以是二叉樹中某一節點到樹中任意一個節點的所經過的路徑，不允許重複經過一個節點，不必經過根節點
Python
1.首先判斷左子樹的和，如果是負數就返回0
2.然後判斷右子樹的和，如果是負數就返回0
3.左右子樹與根節點的值求和作為局部最大值
4.與歷史局部最大值比較得到所有種的最大值
5.返回給上一層時只能選擇一個子樹，返回根節點值加左右子樹的最大值
def maxPathSum(self, root):
if root is None:
return 0
left=max(0,self.maxPathSum(root.left)) #左子樹的和，如果是負數就返回0
right=max(0,self.maxPathSum(root.right)) #右子樹的和，如果是負數就返回0
#左右子樹與根節點的值求和作為局部最大值 / 與歷史局部最大值比較得到所有種的最大值
self.maxsum=max(self.maxsum,root.val+left+right)
retrun root.val+max(left,max) #返回給上一層時只能選擇一個子樹，返回根節點值加左右子樹的最大值C++
函數 maxPathSum，其中 maxSum 是一個引用類型的參數，用於保存最大路徑和。 maxPathSum 函數返回以當前節點為路徑終點的最大路徑和，然後將其與左右子樹的路徑和相加再加上當前節點的值，更新 maxSum。
在遞歸時，如果當前節點為空，返回 0。否則，計算左右子樹的最大路徑和（若子樹最大路徑和小於 0，則返回 0），並將左右子樹的最大路徑和相加再加上當前節點的值，更新 maxSum。最後返回以當前節點為路徑終點的最大路徑和，供父節點使用。
class Solution {
public:
int maxPathSum(TreeNode* root) {
int maxSum = INT_MIN;
maxPathSum(root, maxSum);
return maxSum;
}
int maxPathSum(TreeNode* root, int& maxSum) {
if (!root) {
return 0;
}
int leftSum = max(0, maxPathSum(root->left, maxSum));
int rightSum = max(0, maxPathSum(root->right, maxSum));
maxSum = max(maxSum, leftSum + rightSum + root->val);
return max(leftSum, rightSum) + root->val;
}
};