124.md

124. Binary Tree Maximum Path Sum

Solution 1

# DFS

# 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 = root.val
        _ = self.dfs(root)
        return self.ans

    def dfs(self, root):
        if root.left is not None:
            ans1 = self.dfs(root.left)
        if root.right is not None:
            ans2 = self.dfs(root.right)
        cur_ans = root.val
        if root.left is not None:
            cur_ans += max(0, ans1)
        if root.right is not None:
            cur_ans += max(0, ans2)
        self.ans = max(self.ans, cur_ans)
        ret_val = root.val
        if root.left is not None:
            ret_val = max(ret_val, root.val + ans1)
        if root.right is not None:
            ret_val = max(ret_val, root.val + ans2)
        return ret_val