0129.求根节点到叶节点数字之和

https://leetcode.cn/problems/sum-root-to-leaf-numbers/

方法一：前序遍历

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumNumbers(root *TreeNode) int {
	var dfs func(root *TreeNode, value int) int
	dfs = func(root *TreeNode, value int) int {
		if root == nil {
			return 0
		}
		preSum := value*10 + root.Val
		if root.Left == nil && root.Right == nil {
			return preSum
		}
		return dfs(root.Left, preSum) + dfs(root.Right, preSum)
	}
	return dfs(root, 0)
}