124. Binary Tree Maximum Path Sum
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: 6Example 2:
Input: [-10,9,20,null,null,15,7]
-10
/ \
9 20
/ \
15 7
Output: 42Solution
这题主要是要理解 path 的含义。path 定义为从任意起始点开始，通过父子间的连接的一系列点的集合，并且同一条连接不能使用多次。上面第二个例子中，output 对应的path 为 15 -> 20 -> 7（或7 ->20 -> 15）, 而绝不是 20->15->7,因为15与7之间不存在连接，15也不能回到20再到7.
先给一个错误的例子，这个例子实现的是最大子树和，而不仅仅是path 它的思路为： 1. 返回的数据组中记录的是{包含当前节点的最大子树和, 当前节点的maxPathSum} 2. 深度遍历，将节点加入后更新返回值 3. root 节点的maxPathSum 即为解
/**
* 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]};
int[] r4 = new int[]{add(node.val, left[0]), add(node.val, left[0])};
int[] r5 = new int[]{add(node.val, right[0]), add(node.val, right[0])};
int[] r6 = new int[]{add(add(node.val, left[0]), right[0]), add(add(node.val, left[0]), right[0])};
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;
}
}这个程序在测试case [5,4,8,11,null,13,4,7,2,null,null,null,1] 上失败了，输出了55，实际应是48.
在discuss区很多网友也有这个疑问，不过明白了 path 的含义就能看出我们程序的问题，返回值应该是{包含当前节点的最大path和,当前节点的maxPathSum}，这个 包含当前节点的最大path和 由于需要parent 使用，因此它不能既向左又向右，而是要么向左要么向右，要么只有自己三者的最大值，即 max(node,node+left,node+right)。
因此修改后的程序：
/**
* 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 rl = Math.max(Math.max(node.val, add(node.val, left[0])), add(node.val, right[0]));
int r1 = node.val;
int r2 = left[1];
int r3 = right[1];
int r4 = add(node.val, left[0]);
int r5 = add(node.val, right[0]);
int r6 = add(add(node.val, left[0]), right[0]);
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;
}
}这个accepted 了，但是运行时间惨不忍睹47ms，只打败了 1% 的人。 第一次觉得可能和 Stream 的使用有关，换成了 array + sort的形式，运行时间减少了10ms，依然惨不忍睹。
再观察一下，rl 其实已经是r1,r4,r5的比较结果，只需要将其与r2,r3,r6比较即可，没有必要使用排序这么重量级的手段。 最终程序如下：
/**
* 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 rl = Math.max(Math.max(node.val, add(node.val, left[0])), add(node.val, right[0]));
int rr = Math.max(rl, left[1]);
rr = Math.max(rr, right[1]);
rr = Math.max(rr, add(add(node.val, left[0]), right[0]));
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;
}
}运行时间变为 1ms， 打败99.7%。
时间复杂度分析： T(n) = 2T(n/2) + const
因此 T(n) = O(n)