leetcode -- Sum Root to Leaf Numbers

6892 단어 LeetCode
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  * Definition for binary tree
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {
11     public int sumNumbers(TreeNode root) {
12         // Start typing your Java solution below
13         // DO NOT write main() function
14         if(root == null){
15             return 0;
16         }
17         ArrayList<String> result = new ArrayList<String>();
18         StringBuilder sb = new StringBuilder();
19         int sum = 0;
20         dfs(root, sb, result);
21         for(int i = 0; i < result.size(); i++){
22             sum += Integer.parseInt(result.get(i));
23         }
24         return sum;
25     }
26     
27     public void dfs(TreeNode root, StringBuilder sb, ArrayList<String> result){
28         if(root.left == null && root.right == null){
29             sb.append(root.val);
30             result.add(sb.toString());
31             sb.deleteCharAt(sb.length() - 1);
32             return;
33         }
34         sb.append(root.val);
35         if(root.left != null){
36             //sb.append(root.left.val);
37             dfs(root.left, sb, result);
38             //sb.deleteCharAt(sb.length() - 1);
39         }
40         if(root.right != null){
41             //sb.append(root.right.val);
42             dfs(root.right, sb, result);
43             //sb.deleteCharAt(sb.length() - 1);
44         }
45         sb.deleteCharAt(sb.length() - 1);
46     }
47 }

좋은 웹페이지 즐겨찾기