Binary tree maximum path sum#

Levels: level-5

Data structures: tree

Algorithms: dfs

Description#

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.

Examples#

text

1Input: [1,2,3]
2
3       1
4      / \
5     2   3
6
7Output: 6

text

1Input: [-10,9,20,null,null,15,7]
2
3   -10
4   / \
5  9  20
6    /  \
7   15   7
8
9Output: 42

Python Solution#

 1class TreeNode(object):
 2    def __init__(self, x):
 3        self.val = x
 4        self.left = None
 5        self.right = None
 6
 7
 8class Solution(object):
 9    def maxPathSum(self, root):
10        """
11        :type root: TreeNode
12        :rtype: int
13        """
14        def maxend(node):
15            if not node:
16                return 0
17            left = maxend(node.left)
18            right = maxend(node.right)
19            self.max = max(self.max, left + node.val + right)
20            return max(node.val + max(left, right), 0)
21
22        self.max = None
23        maxend(root)
24        return self.max