>

自由软件精神——“自由、开放、分享”。自由软件自诞生之日起,就秉承了学术自由的思想,信奉科学无国界,知识应该全人类共享。

ubuntu精神——人道待人,天下共享连接人人的信念。具有 ubuntu 精神的人心胸开阔,乐于助人,见贤思齐而不忌妒贤能......

leetcode刷题 Binary Tree Maximum Path Sum

 

iven a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

       1
      / \
     2   3

 

Return 6.


public class Solution {
	public int maxPathSum(TreeNode root) {
		int max[] = new int[1]; 
		max[0] = Integer.MIN_VALUE;
		calculateSum(root, max);
		return max[0];
	}
 
	public int calculateSum(TreeNode root, int[] max) {
		if (root == null)
			return 0;
 
		int left = calculateSum(root.left, max);
		int right = calculateSum(root.right, max);
 
		int current = Math.max(root.val, Math.max(root.val + left, root.val + right));
 
		max[0] = Math.max(max[0], Math.max(current, left + root.val + right));
 
		return current;
	}
}

 

 

__author__ = 'bone-lee'

# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param root, a tree node
    # @return an integer
    def maxPathSum(self, root):
        assert root
        (max_sum,end_sum)=self.max_path_sum_helper(root)
        return max_sum

    def max_path_sum_helper(self,root):
        if root is None: return (float('-inf'),float('-inf'))
        left_max_sum,left_end_sum=self.max_path_sum_helper(root.left)
        right_max_sum,right_end_sum=self.max_path_sum_helper(root.right)
        end_sum=max(left_end_sum+root.val,right_end_sum+root.val,root.val)
        max_sum=max(end_sum,left_max_sum,right_max_sum,left_end_sum+root.val+right_end_sum)
        return (max_sum,end_sum)

Meta

发布: 十二月 3, 2014

作者: Bone Lee 李智华

评论:  

字数统计: 231

下一篇: leetcode刷题 Largest Rectangle in Histogram

上一篇: leetcode刷题 Minimum Window Substring

Bookmark and Share

Tags

code leetcode python

comments powered by Disqus

返回顶部