H*M
发帖数: 1268 | 1 Given a value and a binary search tree.
Print all the paths(if there exists more than one) which sum up to that valu
e. It can be any path in the tree. It doesn't have to be from the root.
我理解是这个path可以是其中任意一截,不用包括头尾 | H*M
发帖数: 1268 | 2 感觉这题不太容易
就是一个unsorted array,求出所有consecutive sub array和为sum都不trivial
valu
【在 H*M 的大作中提到】
: Given a value and a binary search tree.
: Print all the paths(if there exists more than one) which sum up to that valu
: e. It can be any path in the tree. It doesn't have to be from the root.
: 我理解是这个path可以是其中任意一截,不用包括头尾
| h***r
发帖数: 726 | 3 下面这个有线性解吧。
对原体来说，可能应该对长度循环： total time complexity O(n log^2 n). assume
tree
is balanced.
长度为1： 退化为search, trival, O(logn)
长度为2：
let's say the input is x, we use t.v, t.left.v t.right.v for the value at
node t, t.left, t.right
从根遍历树(using a queue)，但是加上下面的一些speedup:
init: q.push_back(root), t = q.pop()
a = t.v + t.left.v
b = t.v + t.right.v
if (x < a) {
push_back(t.left);
} else if (x == a) {
output this path;
push_back(t.left.right);
} else if (x betwen a, b) {
pus
【在 H*M 的大作中提到】
: 感觉这题不太容易
: 就是一个unsorted array,求出所有consecutive sub array和为sum都不trivial
:
: valu
| h***r
发帖数: 726 | 4 another simple O(n log^2 n) algorithm (assume tree is balanced)
for (each node) { // n
for each path from the node toward the root { // logn
output the path if the sum of the path == input value //
logn
}
}
tree
【在 h***r 的大作中提到】
: 下面这个有线性解吧。
: 对原体来说，可能应该对长度循环： total time complexity O(n log^2 n). assume
: tree
: is balanced.
: 长度为1： 退化为search, trival, O(logn)
: 长度为2：
: let's say the input is x, we use t.v, t.left.v t.right.v for the value at
: node t, t.left, t.right
: 从根遍历树(using a queue)，但是加上下面的一些speedup:
: init: q.push_back(root), t = q.pop()
| H*M
发帖数: 1268 | 5 are you kidding?
【在 h***r 的大作中提到】
: another simple O(n log^2 n) algorithm (assume tree is balanced)
: for (each node) { // n
: for each path from the node toward the root { // logn
: output the path if the sum of the path == input value //
: logn
: }
: }
:
: tree
| S*********N
发帖数: 6151 | 6
valu
if it is sorted, then the given value will provide some boundary.
【在 H*M 的大作中提到】
: Given a value and a binary search tree.
: Print all the paths(if there exists more than one) which sum up to that valu
: e. It can be any path in the tree. It doesn't have to be from the root.
: 我理解是这个path可以是其中任意一截,不用包括头尾
| b***e
发帖数: 1419 | 7 If all the numbers are non-negative, then it's trivial, just traverse
the list one with two pointers i and j, and bookkeeping the sum
between the ith element and the jth element. This takes O(n).
【在 H*M 的大作中提到】
: 感觉这题不太容易
: 就是一个unsorted array,求出所有consecutive sub array和为sum都不trivial
:
: valu
| H*****L
发帖数: 5705 | 8 ft..这题没这么简单吧
这个方法不对，而且复杂度也不是O(n)
【在 b***e 的大作中提到】
: If all the numbers are non-negative, then it's trivial, just traverse
: the list one with two pointers i and j, and bookkeeping the sum
: between the ith element and the jth element. This takes O(n).
| H*M
发帖数: 1268 | 9 If there can be negative numbers in the array,can we do this:
sum all elements to the left, s[i] = sum of a[j], j=0...i
O(n) here
then sort the sum_array s, for each element in s, s[i], binary_search the v
alue GIVEN_SUM + s[i] to see if that element is in the sum_array s or not. I
f yes, we find it.
O(nlgn)
【在 b***e 的大作中提到】
: If all the numbers are non-negative, then it's trivial, just traverse
: the list one with two pointers i and j, and bookkeeping the sum
: between the ith element and the jth element. This takes O(n).
| b***e
发帖数: 1419 | 10 是.
the v
not. I
【在 H*M 的大作中提到】
: If there can be negative numbers in the array,can we do this:
: sum all elements to the left, s[i] = sum of a[j], j=0...i
: O(n) here
: then sort the sum_array s, for each element in s, s[i], binary_search the v
: alue GIVEN_SUM + s[i] to see if that element is in the sum_array s or not. I
: f yes, we find it.
: O(nlgn)
| r**u
发帖数: 1567 | 11 这个path必须是一个非叶节点到叶子节点，还是任意俩个node of the tree都行？
valu
【在 H*M 的大作中提到】
: Given a value and a binary search tree.
: Print all the paths(if there exists more than one) which sum up to that valu
: e. It can be any path in the tree. It doesn't have to be from the root.
: 我理解是这个path可以是其中任意一截,不用包括头尾
| p********7
发帖数: 549 | 12 what is a[i]? is it the in-order traverse array?
the v
not. I
【在 H*M 的大作中提到】
: If there can be negative numbers in the array,can we do this:
: sum all elements to the left, s[i] = sum of a[j], j=0...i
: O(n) here
: then sort the sum_array s, for each element in s, s[i], binary_search the v
: alue GIVEN_SUM + s[i] to see if that element is in the sum_array s or not. I
: f yes, we find it.
: O(nlgn)
| s*******t
发帖数: 248 | 13 I don't think both of your idea will work.
But thanks for sharing your idea.
assume
【在 h***r 的大作中提到】
: 下面这个有线性解吧。
: 对原体来说，可能应该对长度循环： total time complexity O(n log^2 n). assume
: tree
: is balanced.
: 长度为1： 退化为search, trival, O(logn)
: 长度为2：
: let's say the input is x, we use t.v, t.left.v t.right.v for the value at
: node t, t.left, t.right
: 从根遍历树(using a queue)，但是加上下面的一些speedup:
: init: q.push_back(root), t = q.pop()
|
|
