求根到叶子节点数字之和。题意是给一棵二叉树，请根据图示做加法。例子，

Example:

Input: [1,2,3]
    1
   / \
  2   3
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.

Example 2:

Input: [4,9,0,5,1]
    4
   / \
  9   0
 / \
5   1
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.

思路是前序遍历递归做。记录一个变量sum存之前所有的加和，当遍历到当前节点的时候，sum *= 10 再加当前的节点值cur.val。

时间O(n)

空间O(n)

Java实现

 1 class Solution {
 2     int total;
 3 
 4     public int sumNumbers(TreeNode root) {
 5         total = 0;
 6         helper(root, total);
 7         return total;
 8     }
 9 
10     private void helper(TreeNode root, int sum) {
11         if (root == null) {
12             return;
13         }
14         sum = sum * 10 + root.val;
15         if (root.left == null && root.right == null) {
16             total += sum;
17             return;
18         }
19         helper(root.left, sum);
20         helper(root.right, sum);
21     }
22 }

 

JavaScript实现

 1 /**
 2  * @param {TreeNode} root
 3  * @return {number}
 4  */
 5 var sumNumbers = function (root) {
 6     let sum = 0;
 7     if (!root) {
 8         return 0;
 9     }
10     const dfs = (node, current) => {
11         current = current * 10 + node.val;
12         if (!node.left && !node.right) {
13             sum += current;
14         }
15         if (node.left) {
16             dfs(node.left, current)
17         }
18         if (node.right) {
19             dfs(node.right, current)
20         }
21     }
22     dfs(root, 0);
23     return sum;
24 };