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.
Solution
Recursion
- 最优路径上的节点一定是连续的,不能中断
- 最优路径中一定包含某个子树的根节点
- 写一个递归函数,实现计算根节点到任意点的最大路径和,以及穿过根节点的最大路径和,用一个全局变量保存最优解。
Complexity
这个暂时不知道怎么算。。
Code
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int maxPathSum(TreeNode root) {
int[] res = new int[1];
res[0] = Integer.MIN_VALUE;
maxPathSumRe(root, res);
return res[0];
}
int maxPathSumRe(TreeNode root, int[] res) {
if (root == null) return 0;
int left = maxPathSumRe(root.left, res);
int right = maxPathSumRe(root.right, res);
res[0] = Math.max(res[0], root.val + Math.max(left, 0) + Math.max(right, 0));
return Math.max(root.val, root.val + Math.max(left, right));
}
}