|
| 1 | +packagemedium; |
| 2 | + |
| 3 | +importjava.util.ArrayList; |
| 4 | +importjava.util.List; |
| 5 | + |
| 6 | +importclasses.TreeNode; |
| 7 | + |
| 8 | +publicclassSumRootToLeafNumbers { |
| 9 | +//it could overflow when the tree is very deep/large, so definitely use long |
| 10 | +//let's assume it won't overflow first |
| 11 | +publicintsumNumbers(TreeNoderoot) { |
| 12 | +if(root ==null)return0; |
| 13 | +List<Integer>allNumbers =newArrayList(); |
| 14 | +dfs(root,newStringBuilder(),allNumbers); |
| 15 | +intsum =0; |
| 16 | +for(inti :allNumbers){ |
| 17 | +sum +=i; |
| 18 | + } |
| 19 | +returnsum; |
| 20 | + } |
| 21 | + |
| 22 | +privatevoiddfs(TreeNoderoot,StringBuildersb,List<Integer>allNumbers) { |
| 23 | +sb.append(root.val); |
| 24 | +if(root.left !=null){ |
| 25 | +dfs(root.left,sb,allNumbers); |
| 26 | + } |
| 27 | +if(root.right !=null){ |
| 28 | +dfs(root.right,sb,allNumbers); |
| 29 | + } |
| 30 | +if(root.left ==null &&root.right ==null){ |
| 31 | +allNumbers.add(Integer.parseInt(sb.toString())); |
| 32 | + } |
| 33 | +sb.deleteCharAt(sb.length()-1); |
| 34 | + } |
| 35 | + |
| 36 | +publicstaticvoidmain(String...strings) { |
| 37 | +more_concise_versiontest =newmore_concise_version(); |
| 38 | +TreeNoderoot =newTreeNode(1); |
| 39 | +root.left =newTreeNode(2); |
| 40 | +root.right =newTreeNode(3); |
| 41 | +System.out.println(test.sumNumbers(root)); |
| 42 | + } |
| 43 | +} |
| 44 | + |
| 45 | +classmore_concise_version{ |
| 46 | +publicintsumNumbers(TreeNoderoot) { |
| 47 | +returndfs(root,0); |
| 48 | + } |
| 49 | + |
| 50 | +privateintdfs(TreeNoderoot,intsum) { |
| 51 | +if(root ==null)return0; |
| 52 | +if(root.left ==null &&root.right ==null)returnsum*10+root.val; |
| 53 | +returndfs(root.left,sum*10+root.val) +dfs(root.right,sum*10+root.val); |
| 54 | + } |
| 55 | +} |
| 56 | + |