首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。