# 124. Binary Tree Maximum Path Sum

### Description

Given a non-empty 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 must contain at least one node and does not need to go through the root.

Example 1:

```Input: [1,2,3]

1
/ \
2   3

Output: 6```

Example 2:

```Input: [-10,9,20,null,null,15,7]

-10
/ \
9  20
/  \
15   7

Output: 42```

### Solution

```/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int maxPathSum(TreeNode root) {
return maxAndSum(root)[1];
}

//0:sum 1:max
private int[] maxAndSum(TreeNode node) {
if (node.left == null && node.right == null) {
return new int[]{node.val, node.val};
}
int[] left = new int[]{0, Integer.MIN_VALUE};
if (node.left != null) {
left = maxAndSum(node.left);
}
int[] right = new int[]{0, Integer.MIN_VALUE};
if (node.right != null) {
right = maxAndSum(node.right);
}
int[] r1 = new int[]{node.val, node.val};
int[] r2 = new int[]{add(node.val, left[0]), left[1]};
int[] r3 = new int[]{add(node.val, right[0]), right[1]};
return Stream.of(r1, r2, r3, r4, r5, r6).max(((o1, o2) -> {
if (o1[1] == o2[1]) {
return 0;
}
if (o1[1] == Integer.MIN_VALUE) {
return -1;
} else if (o2[1] == Integer.MIN_VALUE) {
return 1;
}
return o1[1] - o2[1];
})).get();
}

private int add(int a, int b) {
if (a == Integer.MIN_VALUE ) {
return b;
} else if (b == Integer.MIN_VALUE) {
return a;
}
return a+b;
}
}```

```/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int maxPathSum(TreeNode root) {
return maxAndSum(root)[1];
}

//0:sum 1:max
private int[] maxAndSum(TreeNode node) {
if (node.left == null && node.right == null) {
return new int[]{node.val, node.val};
}
int[] left = new int[]{0, Integer.MIN_VALUE};
if (node.left != null) {
left = maxAndSum(node.left);
}
int[] right = new int[]{0, Integer.MIN_VALUE};
if (node.right != null) {
right = maxAndSum(node.right);
}

int r1 = node.val;
int r2 = left[1];
int r3 = right[1];
return Stream.of(r1, r2, r3, r4, r5, r6).max(((o1, o2) -> {
if (o1.equals(o2)) {
return 0;
}
if (o1 == Integer.MIN_VALUE) {
return -1;
} else if (o2 == Integer.MIN_VALUE) {
return 1;
}
return o1 - o2;
})).map(ints -> new int[]{rl, ints}).get();
}

private int add(int a, int b) {
if (a == Integer.MIN_VALUE ) {
return b;
} else if (b == Integer.MIN_VALUE) {
return a;
}
return a+b;
}
}```

```/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int maxPathSum(TreeNode root) {
return maxAndSum(root)[1];
}

//0:sum 1:max
private int[] maxAndSum(TreeNode node) {
if (node.left == null && node.right == null) {
return new int[]{node.val, node.val};
}
int[] left = new int[]{0, Integer.MIN_VALUE};
if (node.left != null) {
left = maxAndSum(node.left);
}
int[] right = new int[]{0, Integer.MIN_VALUE};
if (node.right != null) {
right = maxAndSum(node.right);
}

int rr = Math.max(rl, left[1]);
rr = Math.max(rr, right[1]);

return new int[]{rl, rr};
}

private int add(int a, int b) {
if (a == Integer.MIN_VALUE ) {
return b;
} else if (b == Integer.MIN_VALUE) {
return a;
}
return a+b;
}
}```

0 条评论

——老子

——老子

• ### 冲上云霄，Dubbo Go！

5 月 21 日，经过一年多的孵化，Apache Dubbo 从 Apache 软件基金会毕业，成为 Apache 顶级项目。推荐：厉害了，Dubbo 正式毕业...

——老子

——老子

——老子

• ### 腾讯开源框架TarsCpp-rpc设计分析-client（一）

Tars是腾讯开源的微服务平台，包含了一个高性能的rpc框架和服务治理平台，TarsCpp是其C++版本。对于以C++为主要开发语言，同时还想深入了解rpc和微...

——老子

• ### 做 Java 或者 C++ 开发都应该知道的 lsof 命令

lsof 命令是 Linux 系统的扩展工具，它的含义是 list opened filedesciptor （列出已经打开的文件描述符），在 Linux 系统...

——老子

AmazonSDE II