longest-path-sum.py

# https://binarysearch.com/problems/Longest-Tree-Sum-Path-From-Root-to-Leaf

class Tree:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    # sum_ = sum of path up to but not including this node
    def helper(self, node, sum_, depth):
        if node is None:
            return
        # if leaf, check if deepest leaf yet and if so, update self.result
        if node.left is None and node.right is None:
            if depth > self.max_depth:
                self.max_depth = depth
                self.result = sum_ + node.val
            elif depth == self.max_depth:
                self.result = max(self.result, sum_ + node.val)
                return
        self.helper(node.left, sum_ + node.val, depth+1)
        self.helper(node.right, sum_ + node.val, depth+1)

    def solve(self, root):
        if root is None:
            return 0
        self.result = 0
        self.max_depth = 0
        self.helper(root, 0, 0)
        return self.result