[LeetCode]Binary Tree 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.

题目大意:

给定一棵二叉树,寻找最大路径和。

对于本题,路径指的是从任意起始节点出发沿着父亲-孩子链接到达某个终止节点的节点序列。路径不一定要穿过根节点。

例如:
给定下面的二叉树,

       1
      / \
     2   3

返回6。

解题思路:

DFS(深度优先搜索)

题目中的“路径”中的任意节点只能出现一次。

详见代码

Python代码:

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

class Solution(object):
    def maxPathSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.ans = None
        def search(root):
            if root is None:
                return 0
            leftMax = search(root.left)
            rightMax = search(root.right)
            self.ans = max(max(leftMax, 0) + max(rightMax, 0) + root.val, self.ans)
            return max(leftMax, rightMax, 0) + root.val
        search(root)
        return self.ans

 

本文链接:http://bookshadow.com/weblog/2015/10/27/leetcode-binary-tree-maximum-path-sum/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码

Pingbacks已关闭。

评论
  1. 宋扬 宋扬 发布于 2017年2月23日 17:37 #

    大神, ans=Max( )是怎么比较的, 里面一个参数是Nonetype类型的

  2. Jesse Jesse 发布于 2017年11月28日 03:09 #

    Input: [-3] 这个case fail。
    self.ans = -float('inf') 就对了。

张贴您的评论