# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
    def _pp(self):
        l = self.left.pp() if self.left is not None else "_"
        r = self.right.pp() if self.right is not None else "_"
        return f"({self.val} {l} {r})"
    def pp(x):
        if x is None:
            return "_"
        else:
            return x._pp()
    def MakeTree(xs):
        if len(xs) == 0:
            return None
        outs = [None]*(len(xs)+1)
        j = len(xs)
        while j > 0:
            j //= 2
            for i,x in enumerate(xs[j:]):
                if x is None:
                    outs[i] = None
                else:
                    outs[i] = TreeNode(x,outs[2*i],outs[2*i + 1])
            xs = xs[:j]
            #print(f"{j} {[TreeNode.pp(out) for out in outs]}")
        return outs[0]
  

def maxPathSum(root) -> int:
    memo1 = {} # node -> maxPathSum(node)
    memo2 = {} # node -> noBranch(node)
    def noBranch(node):
        if node in memo2:
            return memo2[node]
        else:
            # returns max sum path that starts at node and goes down the tree
            if node.left == None and node.right == None:
                memo2[node] = node.val
                return node.val
            options = []
            if node.left != None: # left
                left = noBranch(node.left) + node.val
                options.append(left)
            if node.right != None: # right
                right = noBranch(node.right) + node.val
                options.append(right)
            options.append(node.val) # neither
            out = max(options)
            memo2[node] = out
            return out
        
    def withBranch(root):
        # returns max sum path that either includes root or includes one of root's children. May branch at root
        if root.left == None and root.right == None:
            return root.val
        options = []
        if root.left != None: # left
            if root.left not in memo1:
                memo1[root.left] = withBranch(root.left)
            options.append(memo1[root.left])
        if root.right != None: # right
            if root.right not in memo1:
                memo1[root.right] = withBranch(root.right)
            options.append(memo1[root.right])
        if root.left != None and root.right != None:
            options.append(noBranch(root.left) + noBranch(root.right) + root.val)
        options.append(noBranch(root))
        return max(options)

    return withBranch(root)
        

tree = [-10,9,20,None,None,15,7]
t = TreeNode.MakeTree(tree)
t.pp()

'(-10 (9 _ _) (20 (15 _ _) (7 _ _)))'

maxPathSum(t)

42