Question

link

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.

Stats

Frequency 4
Difficulty 2
Adjusted Difficulty 2
Time to use 10 minutes

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is DFS standard question.

Solution

I posted 2 pieces of my code, and 1 best code (from this blog).

Code

First, my solution using List.

int sum = 0;

public int sumNumbers(TreeNode root) {
    dfs(root, new LinkedList<Integer>());
    return sum;
}

private void dfs(TreeNode node, LinkedList<Integer> list) {
    if (node == null) return;
    if (node.left == null && node.right == null) {
        int num = 0;
        for (int i = 0; i < list.size(); i ++)
            num = num * 10 + list.get(i);
        sum += num * 10 + node.val;
        return;
    }
    // if node is not null, not a leaf
    list.add(node.val);
    dfs(node.left, list);
    dfs(node.right, list);
    list.remove(list.size() - 1);
}

Second, previous code refactored, without using list, because it’s not necessary to know the previous path.

int sum = 0;
public int sumNumbers(TreeNode root) {
    dfs(root, 0);
    return sum;
}

private void dfs(TreeNode node, int preVal) {
    if (node == null) return;
	int curVal = preVal * 10 + node.val;
    if (node.left == null && node.right == null) {
        int num = 0;
        sum += curVal;
        return;
    }
    // if node is not null, not a leaf
    dfs(node.left, curVal);
    dfs(node.right, curVal);
}

Third, best solution

public int sumNumbers(TreeNode root) {
    return dfs(root,0);
}

int dfs(TreeNode root, int sum){
    if(root==null) return 0;
    sum=sum*10+root.val;
    if(root.left==null && root.right==null) return sum;
    return dfs(root.left,sum) + dfs(root.right,sum);
}