题目：

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.

 

Hide Tags

链接：  

6/8/2017

3ms, 9%

很长时间想不起来怎么做，把tree想成graph就搞定了

注意

1. 第22行还是要加上叶结点的值

2. 第25，32行需要加上当前节点的值，然后删掉。

1 public class Solution { 2     public int sumNumbers(TreeNode root) { 3         if (root == null) { 4             return 0; 5         } 6         List
     
       ret = new ArrayList
      
       (); 7         List
       
         list = new ArrayList
        
         (); 8         dfs(root, ret, list); 9         int sum = 0;10         for (int i = 0; i < ret.size(); i++) {11             sum += ret.get(i);12         }13         return sum;14     }15     private void dfs(TreeNode root, List
         
           ret, List
          
            list) {16 if (root.left == null && root.right == null) {17 int number = 0;18 for (int i = 0; i < list.size(); i++) {19 number = number * 10 + list.get(i);20 }21 number = number * 10 + root.val;22 ret.add(number);23 return;24 }25 list.add(root.val);26 if (root.left != null) {27 dfs(root.left, ret, list);28 }29 if (root.right != null) {30 dfs(root.right, ret, list);31 }32 list.remove(list.size() - 1);33 }34 }
          
         
        
       
      
     

别人更简单的做法：

1 public int sumNumbers(TreeNode root) {2     return sum(root, 0);3 }4 5 public int sum(TreeNode n, int s){6     if (n == null) return 0;7     if (n.right == null && n.left == null) return s*10 + n.val;8     return sum(n.left, s*10 + n.val) + sum(n.right, s*10 + n.val);9 }

更多讨论