## 题目描述：

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```

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
``````

Pingbacks已关闭。

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

大神， ans＝Max（ ）是怎么比较的， 里面一个参数是Nonetype类型的

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

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