Problem
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 (Java)
/**
* 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 maxSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
oneSideMaxSum(root);
return maxSum;
}
// preserve the max sum of one side of node "root",
// includig "root" node
private int oneSideMaxSum(TreeNode root) {
if (root == null) {
return 0;
}
int l = oneSideMaxSum(root.left);
int r = oneSideMaxSum(root.right);
maxSum = Math.max(maxSum, root.val + Math.max(l, 0) + Math.max(r, 0));
return root.val + Math.max(0, Math.max(l, r));
}
}
Solution (Javascript)
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var maxPathSum = function(root) {
var max = Number.MIN_SAFE_INTEGER;
var maxSum = function (node) {
if (!node) return 0;
var left = Math.max(maxSum(node.left), 0);
var right = Math.max(maxSum(node.right), 0);
max = Math.max(left + right + node.val, max);
return Math.max(left, right) + node.val;
};
maxSum(root);
return max;
};
Explain:
注意此题找的是路径 path，你用到的节点需要连通在一条路上。
所以 return Math.max(left, right) + node.val 而不是 return left + right + node.val。
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).