# Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path does not need to go through the root.

For example:
Given the below binary tree,

1
/
2   3

Return 6.

## 复杂度

time: O(n), space: O(h)

## 代码

public class Solution {
public int maxPathSum(TreeNode root) {
int[] max = {Integer.MIN_VALUE}; // 全局最大值
helper(root, max);
return max[0];
}

public int helper(TreeNode node, int[] max) {
if (node == null)
return 0;

// 分别返回以左右子node为起始点的路径的最大值
int left = helper(node.left, max);
int right = helper(node.right, max);

// 加上自己本身值后，计算返回值及更新全局最大值
int leftMax = Math.max(0, left);
int rightMax = Math.max(0, right);
max[0] = Math.max(max[0], node.val + leftMax + rightMax);
return node.val + Math.max(leftMax, rightMax);
}
}

1
/
2   3
/
1   8

Return 11(8 + 3).

## 复杂度

time: O(n), space: O(1)

## 代码

public class Solution {
public int maxPathSum(TreeNode root) {
int[] max = {Integer.MIN_VALUE};
helper(root, max);
return max[0];
}

public int[] helper(TreeNode node, int[] max) {
// res[0]表示包含该点的向下路径最大值，res[1]表示不包含该点向下路径最大值
int[] res = new int[2];

if (node == null)
return res;

int[] left = helper(node.left, max);
int[] right = helper(node.right, max);

int leftMax = 0;
int rightMax = 0;

// 包含本身node, 由于最大值路径node不能连接，不可使用left[0]及right[0]
leftMax = Math.max(leftMax, left[1]);
rightMax = Math.max(rightMax, right[1]);
max[0] = Math.max(max[0], node.val + leftMax + rightMax);
res[0] = node.val + Math.max(leftMax, rightMax);

// 不包含本身node, 左右向下路径无论包不包含左右子节点都可以需要考虑
leftMax = 0;
rightMax = 0;
leftMax = Math.max(leftMax, Math.max(left[0], left[1]));
rightMax = Math.max(rightMax, Math.max(right[0], right[1]));
max[0] = Math.max(max[0], leftMax + rightMax);
res[1] = Math.max(leftMax, rightMax);

return res;
}
}