[LeetCode 129]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   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 } }
   
  

?