Monday, July 21, 2014

Sum Root to Leaf Numbers

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.

DFS: 
public class Solution {
    //Time: O(n)
    private int sum = 0;
    public int sumNumbers(TreeNode root) {
        if (root == null) {
            return sum;
        }
        getSum(root, 0);
        return sum;
    }
    
    private void getSum(TreeNode root, int cur) {
        cur = cur * 10 + root.val;
        if (root.left == null && root.right == null) {
            sum += cur;
            return;
        }
        if (root.left != null) {
            getSum(root.left, cur);
        }
        if (root.right != null) {
            getSum(root.right, cur);
        }
    }
}
BFS: 
public class Solution {
    //Time: O(n)
    public int sumNumbers(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        int sum = 0;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        Queue<Integer> queuesum = new LinkedList<Integer>();
        queue.offer(root);
        queuesum.offer(root.val);
        
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            int cursum = queuesum.poll();
            if (cur.left != null) {
                queue.offer(cur.left);
                queuesum.offer(cursum * 10 + cur.left.val);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
                queuesum.offer(cursum * 10 + cur.right.val);
            }
            if (cur.left == null && cur.right == null) {
                sum += cursum;
            }
        }
        return sum;
    }
}

No comments:

Post a Comment