### 题目

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

    1
/ \
2   3


The root-to-leaf path 1->2 represents the number 12. The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

### 自底向上的动态规划把数字收集起来

    1
/ \
2   3


#### 代码

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int sumNumbers(TreeNode root) {
List<List<Integer>> res = dp(root);
int sum = 0;
for (List<Integer> list : res) {
int size = list.size();
for (int i = 0; i < size; i++) {
sum += list.get(i) * (int)Math.pow(10,size-1-i);
}
}
return sum;
}
public List<List<Integer>> dp(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) { return res; }
if (root.left == null && root.right == null) {
return res;
}
List<List<Integer>> left = dp(root.left);
List<List<Integer>> right = dp(root.right);
for (List<Integer> list : left) {
}
for (List<Integer> list: right) {
}
return res;
}
}


### 换成用String记录数字

#### 代码

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int sumNumbers(TreeNode root) {
List<String> res = dp(root);
int sum = 0;
for (String s : res) {
sum += Integer.parseInt(s);
}
return sum;
}
public List<String> dp(TreeNode root) {
List<String> res = new ArrayList<>();
if (root == null) { return res; }
if (root.left == null && root.right == null) {
return res;
}
List<String> left = dp(root.left);
List<String> right = dp(root.right);
for (String s : left) {
}
for (String s : right) {
}
return res;
}
}


#### 结果

List<String>List<List<Integer>>快。但还不是银弹！

### 自顶向下回溯算法

    1
/ \
2   3
/
4


#### 代码

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int sumNumbers(TreeNode root) {
if (root == null) { return 0; }
int[] res = new int[1];
backtracking(root,0,res);
return res[0];
}
public void backtracking(TreeNode root, int sum, int[] res) {
sum = sum * 10 + root.val;
if (root.left == null && root.right == null) { res[0] += sum; }
if (root.left != null) { backtracking(root.left,sum,res); }
if (root.right != null) { backtracking(root.right,sum,res); }
}
}