Sum Root to Leaf Numbers @LeetCode

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.

	package leetcode.combinations;
	import java.util.ArrayList;
	/**
	*
	* Solution: This problem is similar to PathSum II.
	* Condition: when goes to leaf code, calculate number and add to sum.
	* We call use different ways to calculate number. ArrayList is one option.
	*
	* The logic could also be written like this, much more clear. but I like my version more. -- keep same to PathSum II.
	* number.add(root.val);
	* if (root.left == null && root.right == null) {
	* sum += getValue(number);
	* } else {
	* helper(sum, number, root.left);
	* helper(sum, number, root.right);
	* }
	* number.remove(number.size() - 1);
	*
	* Take care: We cannot put sum into helper parameter list, as helper has no return value, sum will only change in sub function!
	* After functions return, sum is still that sum! remove sum in parameter and declare it as class variable outside functions.
	* I made this fault in Convert Sorted List to height balanced BST
	*
	* @author jeffwan
	* @date Feb 16, 2014
	*/
	public class SumNumbers {
	int sum = 0;
	public int sumNumbers(TreeNode root) {
	if (root == null) {
	return 0;
	}
	ArrayList<Integer> list = new ArrayList<Integer>();
	helper(root, list);
	return sum;
	}
	private void helper(TreeNode root, ArrayList<Integer> list) {
	if (root == null) {
	return;
	}
	if (root.left == null && root.right == null) {
	list.add(root.val);
	sum += getValue(list);
	list.remove(list.size() - 1);
	return;
	}
	list.add(root.val);
	helper(root.left, list);
	helper(root.right, list);
	list.remove(list.size() - 1);
	}
	private int getValue(ArrayList<Integer> list) {
	int value = 0;
	for (int i = 0; i < list.size(); i++) {
	value = value * 10 + list.get(i);
	}
	return value;
	}
	private static class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode(int x) { this.val = x; }
	}
	}

view raw SumNumbers.java hosted with ❤ by GitHub