Leetcode[124] Binary Tree Maximum Path Sum
08 Nov 2015###Task1 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.
###Python ####Complex
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class pathSum(object):
def __init__(self, totalSum, passSum):
self.totalSum = totalSum
self.passSum = passSum
class Solution(object):
def maxPathSum(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
profit = self.findMax(root)
return profit.totalSum
def findMax(self, root):
if not root:
imin = (-1) << 31
return pathSum(imin, 0)
l = self.findMax(root.left)
r = self.findMax(root.right)
passCur = max(l.passSum, r.passSum) + root.val
passCur = max(passCur, 0)
totalCur = max(l.totalSum, r.totalSum)
totalCur = max(l.passSum + r.passSum + root.val, totalCur)
return pathSum(totalCur, passCur)
####Simple
class Solution:
# @param root, a tree node
# @return an integer
def maxPathSum(self, root):
if root is None:
return 0
self.max_sum = -9223372036854775808
self.maxPathSum_helper(root, self.max_sum)
return self.max_sum
def maxPathSum_helper(self, root, max_sum):
if root is None:
return 0
left = self.maxPathSum_helper(root.left, max_sum)
right = self.maxPathSum_helper(root.right, max_sum)
root_max = max(root.val, left + root.val, right + root.val)
self.max_sum = max(self.max_sum, root_max, left + right + root.val)
return root_max
###Java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public class NodeValue {
int singleValue;
int maxValue;
NodeValue(int singleValue, int maxValue) {
this.singleValue = singleValue;
this.maxValue = maxValue;
}
}
public int maxPathSum(TreeNode root) {
if (root == null) {
return 0;
}
return maxSumHelper(root).maxValue;
}
public NodeValue maxSumHelper(TreeNode root) {
if (root == null) {
return new NodeValue(0, Integer.MIN_VALUE);
}
NodeValue left = maxSumHelper(root.left);
NodeValue right = maxSumHelper(root.right);
int singleMax = Math.max(left.singleValue, right.singleValue) + root.val;
singleMax = Math.max(singleMax, 0);
int totalMax = Math.max(left.maxValue, right.maxValue);
totalMax = Math.max(totalMax, left.singleValue + right.singleValue + root.val);
return new NodeValue(singleMax, totalMax);
}
}
###Points
- Every recursive call need return two variables: one for the total max sum under this node; one for the max sum pass this node and from only one direction (this is important)
- To save the two vars, either declare one as global var or create an extra class to hold the value