Friday, March 8, 2013

[LeetCode] Sum Root to Leaf Numbers

Thought:
Cache stores the current value including the root. It is not a class variable because we want it not change after sum(root.left) and sum(root.right).

Code:
public class Solution {
    public static int result = 0;
    public int sumNumbers(TreeNode root) {
        result = 0;
        int cache = 0;
        sum(root, cache);
        return result;
    }
    public void sum(TreeNode root, int cache) {
        if (root == null) return;
        cache = cache * 10 + root.val;
        if (root.left == null && root.right == null) result = result + cache;
        sum(root.left, cache);
        sum(root.right, cache);
    }
}

Thought: 
Or we could use normal BFS, keeping the add and remove matched.

Code:
public class Solution {
    public static int result = 0;
    public static int cache = 0;
    public int sumNumbers(TreeNode root) {
        result = 0;
        cache = 0;
        sum(root);
        return result;
    }
    public void sum(TreeNode root) {
        if (root == null) return;
        cache = cache * 10 + root.val;
        if (root.left == null && root.right == null) {
            result = result + cache;
        }
        sum(root.left);
        sum(root.right);
        cache = (cache - root.val) / 10;
    }
}

No comments:

Post a Comment