package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumNumbers(root *TreeNode) int {
	sum := 0
	if root == nil {
		return sum
	}
	sumNumbersHelper(root, 0, &sum)
	return sum
}

func sumNumbersHelper(root *TreeNode, prefix int, sum *int) {
	prefix = prefix*10 + root.Val
	hasLeft, hasRight := root.Left != nil, root.Right != nil
	if hasLeft {
		sumNumbersHelper(root.Left, prefix, sum)
	}
	if hasRight {
		sumNumbersHelper(root.Right, prefix, sum)
	}
	if !hasLeft && !hasRight {
		*sum += prefix
	}
}

// func main() {
// 	println(sumNumbers(sortedArrayToBST([]int{1, 2, 3})))
// }