Leetcode 124 二叉树中的最大路径和
二叉树中的最大路径和(Binary Tree Maximum Path Sum)
路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
示例 1：
输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
示例 2：
输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
提示：
- 树中节点数目范围是
[1, 3 * 10^4] -1000 <= Node.val <= 1000
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
int max2(int a, int b){
return a>b?a:b;
}
int max3(int a, int b, int c){
return max2(max2(a,b),c);
}
int maxPathSumRoot(struct TreeNode* root){
if(root == NULL) return 0;
// 有选 root
// 选左
int left = maxPathSumRoot(root->left) + root->val;
// 选右
int right = maxPathSumRoot(root->right)+root->val;
// 没选root
int result = 0;
return max3(left,right,0);
}
int maxPathSum(struct TreeNode* root){
if (root == NULL) return INT_MIN;
// 经过中间 (root) 的最大路径和
int middle = maxPathSumRoot(root->left) + root->val + maxPathSumRoot(root->right);
// 不经过中间 (root)
int left = maxPathSum(root->left);
int right = maxPathSum(root->right);
return max3(left,middle,right);
}