题目：
给定一个非空二叉树，返回其最大路径和。
本题中，路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
示例 1：
输入：[1,2,3]
1
/ \
2 3
输出：6
示例 2：
输入：[-10,9,20,null,null,15,7]
-10
/
9 20
/
15 7
输出：42
链接：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum
思路：
1、这道题采用二叉树的后序遍历。对于每一个节点，计算其左右子树单侧的最大路径和，通过其左右侧、当前节点的和与之前的最大路径和进行对比，找到当前节点下的最大路径和。上述过程通过递归进行完成
Python代码
import sys
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def __init__(self):
self.ans = -1*sys.maxint-1
def singlePathSum(self, root):
if not root:
return 0
left = max(0, self.singlePathSum(root.left))
right = max(0, self.singlePathSum(root.right))
self.ans = max(self.ans, root.val+left+right)
return root.val + max(left, right) # 单侧下最大路径
def maxPathSum(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.singlePathSum(root)
return self.ans
C++ 代码:
/**
* 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) {}
* };
*/
class Solution {
public:
int ans = INT_MIN;
int singlePathSum(TreeNode* root){
if (root==nullptr) {
return 0;
}
int left = max(0, singlePathSum(root->left));
int right = max(0, singlePathSum(root->right));
ans = max(ans, root->val+left+right);
return root->val+max(left, right);
}
int maxPathSum(TreeNode* root) {
singlePathSum(root);
return ans;
}
};
