binary tree, sum of 2 nodes == given number - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

binary tree, sum of 2 nodes == given number

binary tree, sum of 2 nodes == given number# JobHunting - 待字闺中

r*e2012-11-12 08:11

1 楼

Given a binary tree, find a pair of nodes whose sum is the given target
value. Find all solutions.
Any idea to use as space as possible? thanks! :)

C*U2012-11-12 08:11

2 楼

Do you have parent pointer?
predecessor and succesor?

【在 r*****e 的大作中提到】

: Given a binary tree, find a pair of nodes whose sum is the given target
: value. Find all solutions.
: Any idea to use as space as possible? thanks! :)

e*e2012-11-12 08:11

3 楼

Binary tree 是暴力解法了吧.
Binary search tree is O(log(n)).

c*t2012-11-12 08:11

4 楼

hashmap + traversal ?
time O(n)
space O(n)
看看有没有高人更优化。

【在 r*****e 的大作中提到】

: Given a binary tree, find a pair of nodes whose sum is the given target
: value. Find all solutions.
: Any idea to use as space as possible? thanks! :)

r*e2012-11-12 08:11

5 楼

no parent pointer. the structure is defined below.
struct BTNode{
BTNode* right;
BTNode* left;
int val;
}

【在 C***U 的大作中提到】

: Do you have parent pointer?
: predecessor and succesor?

r*e2012-11-12 08:11

6 楼

恩, 我也只能想到这个了，所以发帖请教高人啊。。

【在 c********t 的大作中提到】

: hashmap + traversal ?
: time O(n)
: space O(n)
: 看看有没有高人更优化。

f*32012-11-12 08:11

7 楼

sorry，即便hashmap 和 traversal 也想不明白，是类似inorder traversal然后把每
个点的值hash到一个array里，再找么？

【在 r*****e 的大作中提到】

: 恩, 我也只能想到这个了，所以发帖请教高人啊。。

p*22012-11-12 08:11

8 楼

two sum.
两个指针一个从前往后，一个从后往前。
实现两个函数，getnext和getprev

c*t2012-11-12 08:11

9 楼

要排序？那就是O(nlogn)了？而且还需要存到array里，至少O(n) space?

【在 p*****2 的大作中提到】

: two sum.
: 两个指针一个从前往后，一个从后往前。
: 实现两个函数，getnext和getprev

p*22012-11-12 08:11

10 楼

不是bst呀这题bst才有意思吧

【在 c********t 的大作中提到】

: 要排序？那就是O(nlogn)了？而且还需要存到array里，至少O(n) space?

h*n2012-11-12 08:11

11 楼

traverse之后不就变成2 sum problem了么
呵呵
如果是BST连sort这一步都不用了
题目有什么要求吗？空间时间方面？

【在 r*****e 的大作中提到】

: Given a binary tree, find a pair of nodes whose sum is the given target
: value. Find all solutions.
: Any idea to use as space as possible? thanks! :)

r*e2012-11-12 08:11

12 楼

确实是变成了2sum.
没有什么空间时间要求，就是想跟大家讨论讨论是否还有什么好方法。

【在 h****n 的大作中提到】

: traverse之后不就变成2 sum problem了么
: 呵呵
: 如果是BST连sort这一步都不用了
: 题目有什么要求吗？空间时间方面？

p*22012-11-12 08:11

13 楼

你确认这题是BT不是BST？

【在 r*****e 的大作中提到】

: 确实是变成了2sum.
: 没有什么空间时间要求，就是想跟大家讨论讨论是否还有什么好方法。

K*n2012-11-12 08:11

14 楼

re
换了tree的马甲，还是two sum

【在 p*****2 的大作中提到】

: two sum.
: 两个指针一个从前往后，一个从后往前。
: 实现两个函数，getnext和getprev

r*e2012-11-12 08:11

15 楼

先是分析BST的case, 然后说，如果BT如何做。。。
很遗憾，没有符合二爷的口味

【在 p*****2 的大作中提到】

:
: 你确认这题是BT不是BST？

p*22012-11-12 08:11

16 楼

BST你是怎么做的？

【在 r*****e 的大作中提到】

: 先是分析BST的case, 然后说，如果BT如何做。。。
: 很遗憾，没有符合二爷的口味

r*e2012-11-12 08:11

17 楼

For BST case, time: O(N), space: O(N)
1) in-order scan the tree into an array,
2) 2sum scan the array
弱问一下，若是用get_next(), get_pre()从两边往中间扫。
具体的get_next()和get_pre()的实现是什么？
(1) 存个临时变量，以及相应的栈？若是如此，每次get_next()的时间是O(1),stack
takes O(N) space.
(2) 不存临时变量，每次binary search the next closest value? time is O(logN),
space is O(1)
If we adopt option (1),for bst case, time is O(N), space is O(N)
If we adopt option (2),for bst case, time is O(NlogN), space is O(1)
不知理解是否正确，请指教

【在 p*****2 的大作中提到】

:
: BST你是怎么做的？

p*22012-11-12 08:11

18 楼

space 我感觉是logn呀

stack
),

【在 r*****e 的大作中提到】

: For BST case, time: O(N), space: O(N)
: 1) in-order scan the tree into an array,
: 2) 2sum scan the array
: 弱问一下，若是用get_next(), get_pre()从两边往中间扫。
: 具体的get_next()和get_pre()的实现是什么？
: (1) 存个临时变量，以及相应的栈？若是如此，每次get_next()的时间是O(1),stack
: takes O(N) space.
: (2) 不存临时变量，每次binary search the next closest value? time is O(logN),
: space is O(1)
: If we adopt option (1),for bst case, time is O(N), space is O(N)

c*t2012-11-12 08:11

19 楼

hashmap key=node.val, value=count 边进hashmap，边找
比如 target是5，读到3，找2，如果没有则put<3,1>, 如果hashmap里有<2,1>，找到匹
配，则（2,3）放入解，map里设<2,0>防止重复用。

【在 f*******3 的大作中提到】

: sorry，即便hashmap 和 traversal 也想不明白，是类似inorder traversal然后把每
: 个点的值hash到一个array里，再找么？

c*t2012-11-12 08:11

20 楼

2爷给zkss bst的解法吧

【在 p*****2 的大作中提到】

: space 我感觉是logn呀
:
: stack
: ),

r*e2012-11-12 08:11

21 楼

对。糊涂了

【在 p*****2 的大作中提到】

: space 我感觉是logn呀
:
: stack
: ),

p*22012-11-12 08:11

22 楼

LZ已经解释过了。O(n)时间，Logn空间

【在 c********t 的大作中提到】

: 2爷给zkss bst的解法吧

c*t2012-11-12 08:11

23 楼

没懂
1) in-order scan the tree into an array,
这第一步，不就是O(n)空间了吗？

【在 r*****e 的大作中提到】

: 对。糊涂了

r*e2012-11-12 08:11

24 楼

那个space O(logN) 的解法是基于二爷的思路，调用get_next(), get_pre()从两头走
向中间。此时，get_next(), get_pre()的实现是基于stack的in-order遍历。
若是一般的in-order，就需要O(N)space.

【在 c********t 的大作中提到】

: 没懂
: 1) in-order scan the tree into an array,
: 这第一步，不就是O(n)空间了吗？