124、二叉树中的最大路径和
给定一个非空二叉树，返回其最大路径和。
本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
示例 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、递归遍历
class Solution {
int max_sum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
maxGain(root);
return max_sum;
}
// 后序递归遍历
private int maxGain(TreeNode node) {
if (node == null) {
return 0;
}
// 计算左右子树中的最大路径和
int left = Math.max(maxGain(node.left),0);
int right = Math.max(maxGain(node.right),0);
// 计算当前路径值
int max_gain = left + right + node.val;
// 更新最大路径值
max_sum = Math.max(max_sum,max_gain);
// 只能选择较大的路径返回
return node.val + Math.max(left,right);
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
