[LeetCode 129]Sum Root to Leaf Numbers

题目链接：sum-root-to-leaf-numbers

import java.util.LinkedList;/** * 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. * */public class SumRootToLeafNumbers {public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) {val = x;}}//递归版//109 / 109 test cases passed.//Status: Accepted//Runtime: 215 ms//Submitted: 0 minutes ago public int sumNumbers(TreeNode root) { return dfs(root, 0); } public int dfs(TreeNode root, int sum) { if(root == null) return 0; if(root.left == null && root.right == null) return root.val + sum * 10;return dfs(root.left, root.val + sum * 10) + dfs(root.right, root.val + sum * 10);}//层次遍历法//109 / 109 test cases passed.//Status: Accepted//Runtime: 234 ms//Submitted: 0 minutes agopublic int sumNumbers1(TreeNode root) {int sum = 0;if(root == null) return sum;LinkedList<TreeNode> queue = new LinkedList<TreeNode>();queue.add(root);while(!queue.isEmpty()) {int levelLen = queue.size();for (int i = 0; i < levelLen; i++) {TreeNode node = queue.removeFirst();if(node.left == null && node.right == null)sum += node.val;if(node.left != null) {node.left.val += node.val * 10;queue.add(node.left);}if(node.right != null) {node.right.val += node.val * 10;queue.add(node.right);}}}return sum;}public static void main(String[] args) {// TODO Auto-generated method stub}}

，人生至少要有两次冲动，一为奋不顾身的爱情，一为说走就走的旅行。