?
?
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 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.
*
*/
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 ago
public int sumNumbers1(TreeNode root) {
int sum = 0;
if(root == null) return sum;
LinkedList
queue = new LinkedList
(); 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 } }
?