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