129. Sum Root to Leaf Numbers

题目

给定一个二叉树的根 root 包含数字 0 到。
从根节点到叶子节点的路径代表一个数字。例如1->2->3代表 123。
返回所有的路径和。

解析

1. 从上往下遍历二叉树的时候，计算每条路径的值
2. 回溯返回左右子树的路径和，累积起来就是整个路径和。

难点在1，从上往下遍历的时候，需要携带当前路径所代表的数字，例如 12, 然后当递归到下一字节点的时候，路径和为12×10 + 3。
采用递归实现，函数原型为 f(node, path_sum) sum

伪代码

path_sum = path_sum*10 + node.val
if node.Left == nil && node.Right == nil
    return path_sum
if node.left != nil
  sum+=f(node.left, path_sum)
if node.right != nil
  sum+=f(node.right, path_sum)
return sum

代码

func sumNumbers(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return f(root, 0)
}

func f(node *TreeNode, sub int) (sum int) {
    sub = sub*10 + node.Val
    if node.Left == nil && node.Right == nil {
        return sub
    }
    if node.Left != nil {
        sum += f(node.Left, sub)
    }
    if node.Right != nil {
        sum += f(node.Right, sub)
    }
    return sum
}