129 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.
Note: A leaf is a node with no children.
Example:
Input: [1,2,3]
1
/ \
2 3
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.
Example 2:
Input: [4,9,0,5,1]
4
/ \
9 0
/ \
5 1
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.
Solution: Recursion¶
Time complexity: O(n) Space complexity: O(h)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int sumNumbers(TreeNode root) {
if (root == null) {
return 0;
}
return sum(root, "");
}
private int sum(TreeNode root, String curr){
if (root.left == null && root.right == null) {
return Integer.parseInt(curr + root.val);
}
int sums = 0;
if (root.left != null) {
sums += sum(root.left, curr + root.val);
}
if (root.right != null) {
sums += sum(root.right, curr + root.val);
}
return sums;
}
}
class Solution {
public:
int sumNumbers(TreeNode* root) {
int ans = 0;
function<void(TreeNode*, int)> traverse = [&](TreeNode* t, int num) {
if (!t) return;
num = num * 10 + t->val;
if (t->left || t->right) {
traverse(t->left, num);
traverse(t->right, num);
} else {
ans += num;
}
};
traverse(root, 0);
return ans;
}
};
public class Solution {
public int longestConsecutive(int[] nums) {
HashSet<Integer> data = new HashSet<Integer>();
for (int i = 0; i < nums.length; i ++) {
data.add(nums[i]);
}
int max = 0;
for (int i = 0; i < nums.length; i ++) {
if (data.contains(nums[i])) {
int count = 1;
int tmp = nums[i] - 1;
while (data.contains(tmp)){
data.remove(tmp);
tmp --;
count ++;
}
tmp = nums[i] + 1;
while (data.contains(tmp)) {
data.remove(tmp);
tmp ++;
count ++;
}
max = Math.max(max, count);
}
}
return max;
}
}
public class Solution {
public int longestConsecutive(int[] nums) {
HashMap<Integer, Integer> left = new HashMap<Integer, Integer>();
HashMap<Integer, Integer> right = new HashMap<Integer, Integer>();
HashSet<Integer> visited = new HashSet<Integer>();
int max = 0;
for (int i = 0; i < nums.length; i ++) {
if (visited.contains(nums[i])) {
continue;
}
if (!right.containsKey(nums[i] - 1) && !left.containsKey(nums[i] + 1)) {
left.put(nums[i], nums[i]);
right.put(nums[i], nums[i]);
max = Math.max(max, 1);
visited.add(nums[i]);
continue;
}
if (right.containsKey(nums[i] - 1) && left.containsKey(nums[i] + 1)) {
int a = right.get(nums[i] - 1);
int b = left.get(nums[i] + 1);
right.remove(nums[i] - 1);
left.remove(nums[i] + 1);
left.put(a, b);
right.put(b, a);
max = Math.max(max, b - a + 1);
visited.add(nums[i]);
continue;
}
if (right.containsKey(nums[i] - 1)) {
int a = right.get(nums[i] - 1);
int b = nums[i] - 1;
right.remove(b);
left.put(a, nums[i]);
right.put(nums[i], a);
max = Math.max(max, b - a + 2);
}
if (left.containsKey(nums[i] + 1)) {
int a = nums[i] + 1;
int b = left.get(nums[i] + 1);
left.remove(a);
left.put(nums[i], b);
right.put(b, nums[i]);
max = Math.max(max, b - a + 2);
}
visited.add(nums[i]);
}
return max;
}
}