首页 > 代码库 > Leetcode: Sum Root to Leaf Numbers

Leetcode: Sum Root to Leaf Numbers

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   3The 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.

难度:60. 这是一道树的题目,一般使用递归来做,主要就是考虑递归条件和结束条件。

 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         if (root == null) return 0;13         ArrayList<Integer> set = new ArrayList<Integer>();14         helper(set, 0, root);15         int sum = 0;16         for (int elem : set) {17             sum = sum + elem;18         }19         return sum;20     }21     22     public void helper(ArrayList<Integer> set, int num, TreeNode n) {23         if (n.left == null && n.right == null) {24             num = num*10 + n.val;25             set.add(num);26             return;27         }28         else {29             num = num*10 + n.val;30             if (n.left != null) helper(set, num, n.left);31             if (n.right != null) helper(set, num, n.right);32         }33     }34 }

贴一个别人的更短的解法:

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

 

Leetcode: Sum Root to Leaf Numbers