@compton_scatter said in Concise Java Solution:
(?=[-,+])
Can you explain why you'd have comma in the regex please?
@compton_scatter said in Concise Java Solution:
(?=[-,+])
Can you explain why you'd have comma in the regex please?
Glad that my post helped^^. I am also surprised that this is an "easy" in LC.
Thank you ! Appreciate you sharing the thinking process:)
@chs5003
I just tried this extreme case with the code posted in the thread. Got Memory Limited Exceed, seems like the recursion went too deep that the stack cannot hold that much. Anyway, I think you are right for the extreme case.
This is an excellent idea and took me some time to figure out the logic behind.
Hope my comment here could help understanding this solution.
The interesting part of this solution is that the prefix is counted from the top(root) to the bottom(leaves), and the result of total count is calculated from the bottom to the top :D
The code below takes 16 ms which is super fast.
public int pathSum(TreeNode root, int sum) {
if (root == null) {
return 0;
}
Map<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
return findPathSum(root, 0, sum, map);
}
private int findPathSum(TreeNode curr, int sum, int target, Map<Integer, Integer> map) {
if (curr == null) {
return 0;
}
// update the prefix sum by adding the current val
sum += curr.val;
// get the number of valid path, ended by the current node
int numPathToCurr = map.getOrDefault(sum-target, 0);
// update the map with the current sum, so the map is good to be passed to the next recursion
map.put(sum, map.getOrDefault(sum, 0) + 1);
// add the 3 parts discussed in 8. together
int res = numPathToCurr + findPathSum(curr.left, sum, target, map)
+ findPathSum(curr.right, sum, target, map);
// restore the map, as the recursion goes from the bottom to the top
map.put(sum, map.get(sum) - 1);
return res;
}
Basically, we only need to take into consideration three possible situations.
When the root is null, return 0 directly. If the left child is a leave, then the result we want to calculate is the value of its left child + the sum of left leaves in its right subtree. If the left child is not a leave, then the result should be composed of the sum of left leaves in the left subtree and the sum of left leaves in the right subtree.
public int sumOfLeftLeaves(TreeNode root) {
if (root == null) return 0;
if (root.left != null && isLeave(root.left)) return root.left.val + sumOfLeftLeaves(root.right);
return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
}
private boolean isLeave(TreeNode root) {
if (root.left == null && root.right == null)
return true;
return false;
}
Got exactly the same code as yours :)
@baifriend
Yeah I had the same concern at first, but then I just realized that in this if condition if(A[i] == i+1 || A[i] <= 0 || A[i] > A.length), he put A[i] > A.length to make sure that we ignore numbers that are larger than the length
@yliu224 Thank you !! You really helped me out