05 August 2008
A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.
The path sum of a path is the sum of the node’s values in the path.
Given the ‘root’ of a binary tree, return the maximum path sum of any path.
Example 1:
1
2
3
4
5
6
7
Input: [1,2,3]
1
/ \
2 3
Output: 6
Example 2:
1
2
3
4
5
6
7
8
9
Input: [-10,9,20,null,null,15,7]
-10
/ \
9 20
/ \
15 7
Output: 42
求二叉树的最大路径，这道题很容易想到DFS，但因为起始位置和结束位置可以是任意位置，所以跟112和113 - Path Sum有点区别，有点难度。我们知道Tree相关的题目一般都用递归来做，树的递归解法一般是二话不说先递归到leaf，然后回溯到root，同时在回溯的过程中处理结点。以给定的例子稍微改变一下来看
1
2
3
4
5
-10
/ \
9 20
/ \
15 7
最长路径为15->9->-10->20，现在递归到了15，接下来回溯到9，这时候以9为root的子树的和为15+9+7=31；然后继续回溯到-10，这个时候以9为root的地方得选一条路径，左路径或右路径，因为叶子结点的sum为15 > 7，所以选左路径15->9->-10而不是7->9->-10，所以对回溯到的每个结点，就用递归函数返回值来定义为：当前结点为root，到leaf的最大路径之和，然后保留全局最大值在参数中，然后返回。
在递归函数中，如果当前结点不存在，那么直接返回0。否则就分别对其左右子节点调用递归函数，由于路径和（是 路径的和，不是某个结点的值）有可能为负数，而我们当然不希望加上负的路径和，所以我们和0相比，取较大的那个，也就是要么不加，要加就加正数。然后来更新全局最大值结果result，就是以左子结点为终点的最大path之和加上以右子结点为终点的最大path之和，还要加上当前结点值，这样就组成了一个条完整的路径。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
* 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 {
int result;
public int maxPathSum(TreeNode root) {
result = Integer.MIN_VALUE;
dfs(root);
return result;
}
private int dfs(TreeNode node) { // 后序遍历
if (node == null) { // 和为0
return 0;
}
int left = Math.max(0, dfs(node.left));
int right = Math.max(0, dfs(node.right));
// 更新遍历在当前节点时的最大路径和
result = Math.max(result, node.val + left + right);
// 选择以当前节点为根的含有最大值的路劲，左或右；返回给上一层递归的父节点作为路径
return node.val + Math.max(left, right);
}
}
这道题的Follow up是打印这个最大路径，这时候递归函数需要返回该路径上所有的结点组成的数组，对左右子节点调用递归函数后得到的是路径上经过的元素组成的数组，需要统计出数组之和，跟0比较，如果小于0，这个和就清零，同时数组清空，然后更新最大路径之和跟数组，最后拼出来返回值的数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
import java.util.ArrayList;
import java.util.List;
public class MaximumSumPath {
public static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
static List<Integer> path;
static int maxSum = 0;
public List<Integer> maxPathSum(TreeNode root) {
if ( root == null) {
return new ArrayList<>();
}
maxSum = Integer.MIN_VALUE;
maxPathSumHelper(root);
return path;
}
private List<Integer> maxPathSumHelper(TreeNode root) {
if ( root == null) {
return new ArrayList<>();
}
List<Integer> currRootPath = new ArrayList<>();
//记录左子树的最大sum和路径
List<Integer> leftSubTree = maxPathSumHelper(root.left);
int leftTreeSum = Math.max(0, leftSubTree.stream().mapToInt(l -> l).sum());
int currSum = leftTreeSum;
if ( leftTreeSum > 0) {
currRootPath.addAll(leftSubTree);
}
currSum += root.val;
currRootPath.add(root.val);
// 记录右子树的最大sum和路径
List<Integer> rightTree = maxPathSumHelper(root.right);
int rightTreeSum = Math.max(0, rightTree.stream().mapToInt( l -> l ).sum());
currSum += rightTreeSum;
if ( rightTreeSum > 0) {
currRootPath.addAll(rightTree);
}
//以当前结点为根，是否更新最大sum和相应的路径
if ( currSum > maxSum) {
path = new ArrayList<>();
path.addAll(currRootPath);
maxSum = currSum;
}
// 最后比较，根据当前结点为根的情况下，选择路径，左或右
if ( leftTreeSum > rightTreeSum) {
currRootPath.removeAll(rightTree);
} else if ( rightTreeSum > leftTreeSum) {
currRootPath.removeAll(leftSubTree);
}
return currRootPath;
}
public static void main(String args[]) {
TreeNode root = new TreeNode(-10);
root.left = new TreeNode(9);
root.right = new TreeNode(20);
root.right.left = new TreeNode(15);
root.right.right = new TreeNode(7);
new MaximumSumPath().maxPathSum(root).forEach(t -> System.out.print( t + " "));
}
}