Solution for https://www.interviewbit.com/problems/max-sum-path-in-binary-tree/

max_sum_path.py

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

class Solution:
    # @param A : root node of tree
    # @return an integer
    def __init__(self):
        self.maxsum = -2**31

    def dfs(self, node):
        if not node.left and not node.right:
            self.maxsum = max(self.maxsum, node.val)
            return node.val
        else:
            if node.left and node.right:
                tleft = self.dfs(node.left)
                tright = self.dfs(node.right)
                self.maxsum = max(self.maxsum, node.val, node.val+tleft+tright)
                return max(tleft, tright)+node.val
            elif node.left:
                tleft = self.dfs(node.left)
                self.maxsum = max(self.maxsum, node.val, node.val+tleft)
                return node.val+tleft
            else:                    
                tright = self.dfs(node.right)
                self.maxsum = max(self.maxsum, node.val, node.val+tright)
                return node.val+tright

    def maxPathSum(self, A):
        self.dfs(A)
        return self.maxsum

if __name__ == '__main__':
    t = TreeNode(-1)
    t.left = TreeNode(-2)
    t.left.left = TreeNode(-3)
    t.left.right = TreeNode(-4)
    t.left.right.left = TreeNode(-5)
    s = Solution()
    assert s.maxPathSum(t) == -1
    t = TreeNode(1)
    t.left = TreeNode(2)
    t.left.left = TreeNode(3)
    t.left.right = TreeNode(4)
    t.left.right.left = TreeNode(5)
    s = Solution()
    assert s.maxPathSum(t) == 14