二叉树最大路径和问题
地址：https://leetcode.cn/problems/binary-tree-maximum-path-sum/submissions/
没有一次AC，原因是忽略了路径包含根节点的两种情况(两种：根节点为起点，根节点在中间)。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
static class NodeCalcResult {
int maxSinglePathSum; // 以根节点为起点的最大路径和(空节点返回0)
int maxPathSum; // 该节点及以下最大路径和(空节点返回Integer.MIN_VALUE)
public NodeCalcResult(int maxSinglePathSum, int maxPathSum) {
this.maxSinglePathSum = maxSinglePathSum;
this.maxPathSum = maxPathSum;
}
}
private NodeCalcResult calcNodeSums(TreeNode root) {
if (root == null) {
return new NodeCalcResult(0, Integer.MIN_VALUE);
}
// 路径全在左子树的情况
// 路径全在右子树的情况
// 路径包含根节点的情况(两种：根节点为起点，根节点在中间)
NodeCalcResult left = calcNodeSums(root.left);
NodeCalcResult right = calcNodeSums(root.right);
int maxSinglePathSum = root.val + Math.max(0, Math.max(left.maxSinglePathSum, right.maxSinglePathSum));
int maxPathSumIncludesRoot = Math.max(maxSinglePathSum, root.val + Math.max(0, left.maxSinglePathSum) + Math.max(0, right.maxSinglePathSum));
int maxPathSum = Math.max(maxPathSumIncludesRoot, Math.max(left.maxPathSum, right.maxPathSum));
return new NodeCalcResult(maxSinglePathSum, maxPathSum);
}
public int maxPathSum(TreeNode root) {
return calcNodeSums(root).maxPathSum;
}
}
