package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxPathSum(root *TreeNode) int {
	maxInt := func(x, y int) int {
		if x > y {
			return x
		}
		return y
	}
	var recurse func(*TreeNode) int
	max := root.Val
	recurse = func(root *TreeNode) int { // Sum every path bottom-up is the key
		if root == nil {
			return 0
		}
		maxL := maxInt(0, recurse(root.Left)) // 0 means do not pick the path
		maxR := maxInt(0, recurse(root.Right))
		max = maxInt(max, root.Val+maxL+maxR)
		return root.Val + maxInt(maxL, maxR)
	}
	recurse(root)
	return max
}

// func main() {
// 	tree := toBinaryTree(newInt(-10), newInt(9), newInt(20), nil, nil, newInt(15), newInt(7))
// 	println(maxPathSum(tree), 42)
// 	tree = toBinaryTree(newInt(1), newInt(2), newInt(3))
// 	println(maxPathSum(tree), 6)
// }