124. Binary Tree Maximum Path Sum

Information

  • Diffculty: Hard

  • Created: 2020-01-12 17:13:18

  • Last Motified: 2020-01-12 17:13:18

  • Tags: Tree, Depth-first Search

Intuition

Based on the description of this problem, the path of a tree could be defined by 3 nodes, the sub-root node, the left virtual leaf node and the right virtual leaf. And we could get the sum by traveral 2 path, one from the left virtual leaf to the sub-root, another from the right virtual leaf to the sub-root.

So this problem could be solved using DFS with the code like below. The _helper method is for DFS. The return value of this method is the maximum path from the node to any nodes in its subtree.

Solution

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

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        self.maxpath = root.val
        self._helper(root)
        return self.maxpath

    def _helper(self, node):
        if node is None:
            return 0
        l = self._helper(node.left)
        r = self._helper(node.right)
        self.maxpath = max(
            self.maxpath,
            node.val,
            node.val + l,
            node.val + r,
            node.val + r + l
        )
        return max(l, r, 0) + node.val