Y********f
发帖数: 410 | 1 除了recursion外只能有O(1)的extra space。有什么好的方法。
我的想法是用iterative方法同时in order访问两个树，比较节点大小，打印小的，然
后找到该节点的下一个节点。但是需要O(lgN)的space。 |
w****x
发帖数: 2483 | 2
把bst化为linked list然后再用merge sort的逻辑打印, 前提是bst化为linked list的
递归栈空间不算
【在 Y********f 的大作中提到】
: 除了recursion外只能有O(1)的extra space。有什么好的方法。
: 我的想法是用iterative方法同时in order访问两个树，比较节点大小，打印小的，然
: 后找到该节点的下一个节点。但是需要O(lgN)的space。
|
b***i
发帖数: 3043 | 3 可以用recursion吗？
可以就好办。
【在 Y********f 的大作中提到】
: 除了recursion外只能有O(1)的extra space。有什么好的方法。
: 我的想法是用iterative方法同时in order访问两个树，比较节点大小，打印小的，然
: 后找到该节点的下一个节点。但是需要O(lgN)的space。
|
T******7
发帖数: 1419 | 4 愿问详情
【在 b***i 的大作中提到】
: 可以用recursion吗？
: 可以就好办。
|
p*****2
发帖数: 21240 | |
w****x
发帖数: 2483 | 6
two thread也要堆栈啊
【在 p*****2 的大作中提到】
: 可以用two threads吗？
|
p*****2
发帖数: 21240 | 7
不是有O(1)的traverse吗？
【在 w****x 的大作中提到】
:
: two thread也要堆栈啊
|
w****x
发帖数: 2483 | 8
没有parent怎么O(1)?
【在 p*****2 的大作中提到】
:
: 不是有O(1)的traverse吗？
|
C***U
发帖数: 2406 | 9 晕
我不是刚发过一个帖子么
呵呵
【在 w****x 的大作中提到】
:
: 没有parent怎么O(1)?
|
i******e
发帖数: 273 | 10 用Morris In-order traversal 可以实现不用栈 O(1)空间复杂度。
可是如何实现两个遍历操作之间的同步？如果用两个线程分别遍历两个BST，每遍历一
个结点难道就让这个线程sleep吗？ |
|
|
i******e
发帖数: 273 | 11 用Morris In-order traversal 可以实现不用栈 O(1)空间复杂度。
可是如何实现两个遍历操作之间的同步？如果用两个线程分别遍历两个BST，每遍历一
个结点难道就让这个线程sleep吗？ |
i******e
发帖数: 273 | 12 用Morris In-order traversal 可以实现不用栈 O(1)空间复杂度。
可是如何实现两个遍历操作之间的同步？如果用两个线程分别遍历两个BST，每遍历一
个结点难道就让这个线程sleep吗？ |
Y********f
发帖数: 410 | 13 two thread的话仅仅要用到mutex/cond以及另外几个临时变量吧
【在 w****x 的大作中提到】
:
: 没有parent怎么O(1)?
|
Y********f
发帖数: 410 | 14 只要不是recursive控制同步还是比较简单吧。
【在 i******e 的大作中提到】
: 用Morris In-order traversal 可以实现不用栈 O(1)空间复杂度。
: 可是如何实现两个遍历操作之间的同步？如果用两个线程分别遍历两个BST，每遍历一
: 个结点难道就让这个线程sleep吗？
|
i******e
发帖数: 273 | 15 是呀。这不是和producer-consumer model有点类似吗？ 当一个线程遍历了一个结点之
后block自己同时signal另一个线程遍历另一BST的下一个结点然后比较直到两棵树都遍
历完。
如果有parent指针可以实现getNextNode()函数（O(1)操作）， 可以分别对两棵BST分
别扫描， 就不需要线程同步的方法了。
你说用iterative方法需要O(lgN)的space。 为什么？ |
p*****2
发帖数: 21240 | 16 还有一个办法就是实现getNext
这样单进程就可以完成。 |
Y********f
发帖数: 410 | 17 iterative方法需要自己维护一个栈吧。当然上面提到的morris方法不用，但是比较复
杂，面试应该不会写这个。
【在 i******e 的大作中提到】
: 是呀。这不是和producer-consumer model有点类似吗？ 当一个线程遍历了一个结点之
: 后block自己同时signal另一个线程遍历另一BST的下一个结点然后比较直到两棵树都遍
: 历完。
: 如果有parent指针可以实现getNextNode()函数（O(1)操作）， 可以分别对两棵BST分
: 别扫描， 就不需要线程同步的方法了。
: 你说用iterative方法需要O(lgN)的space。 为什么？
|
p*****2
发帖数: 21240 | 18
其实也还好
public TreeNode getNext()
{
while(current!=null)
{
TreeNode prev=getPrev();
if(prev==null || prev.right==current)
{
TreeNode ans=current;
current=current.right;
if(prev!=null)
prev.right=null;
return ans;
}
prev.right=current;
current=current.left;
}
return null;
}
【在 Y********f 的大作中提到】
: iterative方法需要自己维护一个栈吧。当然上面提到的morris方法不用，但是比较复
: 杂，面试应该不会写这个。
|
b***i
发帖数: 3043 | 19 一个方案是两个线程。
另一个方案，就是看楼主的题目是不是就是要求可以用recursion，不然我说了，然后
再加上各种额外的限制不就不行了？
方法是这样的，traverse1(int seq, Node * node) 将返回node为头的从小开始第seq
个数。
main的程序写个循环什么的，分别从两个BST读入第0个数字，第1个数字什么的。然后
比较，直到最后。这样当然很浪费，每次都要从头寻找，但是要求就是这样，有什么办
法。
【在 T******7 的大作中提到】
: 愿问详情
|
g*********e
发帖数: 14401 | 20 用俩个thread 或者goto语句？hoho |
|
|
g*********e
发帖数: 14401 | 21 用俩个thread 或者goto语句？hoho |
Y********f
发帖数: 410 | 22 学习了，今天花时间仔细看了一下morris traversal，同时练习了一下，测试了一个
case。
Node *getNext(Node* &bst)
{
Node *cur = bst;
while(cur)
{
if (cur->lch == NULL)
{
bst = cur->rch;
return cur;
}
Node *prev = cur->lch;
while(prev->rch && prev->rch != cur)
prev = prev->rch;
if (!prev->rch)
{
prev->rch = cur;
cur = cur->lch;
}
else
{
prev->rch = NULL;
bst = cur->rch;
return cur;
}
}
return NULL;
}
void print2Bst(Node *bst1, Node *bst2)
{
Node *node1 = getNext(bst1);
Node *node2 = getNext(bst2);
while(node1 && node2)
{
if (node1->value < node2->value)
{
cout << node1->value <<" ";
node1 = getNext(bst1);
}
else
{
cout << node2->value << " ";
node2 = getNext(bst2);
}
}
Node *remainBst = node1 ? bst1 : bst2;
Node *node = node1 ? node1 : node2;
while(node)
{
cout << node->value << " ";
node = getNext(remainBst);
}
cout << endl;
}
我这个里面getNext的reference不太好，改变了原来的输入，不过不想改了。
【在 p*****2 的大作中提到】
:
: 其实也还好
: public TreeNode getNext()
: {
: while(current!=null)
: {
: TreeNode prev=getPrev();
: if(prev==null || prev.right==current)
: {
: TreeNode ans=current;
|
e****e
发帖数: 418 | 23 我来个Recursion code，欢迎指正：
public void print(TreeNode n1, TreeNode n2) {
if ( n1 == null && n2 == null )
return;
else if ( n1 == null && n2 != null )
print(n2);
else if ( n1 != null && n2 == null )
print(n1);
else {
print(n1.left, n2.left)
if( n1.val > n2.val) {
println(n2.val);
println(n1.val);
} else{
println(n1.val);
println(n2.val);
}
print(n1.right, n2.right)
}
}
private void print(TreeNode n) {
if ( n == null )
return;
print(n.left);
println(n.val);
print(n.right);
} |
p*****2
发帖数: 21240 | 24
感觉这个code挺悬的。
【在 e****e 的大作中提到】
: 我来个Recursion code，欢迎指正：
: public void print(TreeNode n1, TreeNode n2) {
: if ( n1 == null && n2 == null )
: return;
: else if ( n1 == null && n2 != null )
: print(n2);
: else if ( n1 != null && n2 == null )
: print(n1);
: else {
: print(n1.left, n2.left)
|
e****e
发帖数: 418 | 25 二爷详细说说。
【在 p*****2 的大作中提到】
:
: 感觉这个code挺悬的。
|
f*********d
发帖数: 140 | 26 //我上个代码吧, 没有测试过, 有错误或者bug请指出。。。
//这里假设所有节点的值都不一样, 如果存在一样的节点值, 需要一点修改。。。
struct BSTNode {
BSTNode* left;
BSTNode* right;
int val;
}
//print open interval (min_val, max_val) in r
void PrintBST(BSTNode* r, int min_val, int max_val)
{
if(r == NULL) return;
if(r->val <= min_val) PrintBST(r->right, min_val, max_val);
else if(r->val >= max_val) PrintBST(r->left, min_val, max_val);
else {
PrintBST(r->left, min_val, r->val);
cout << r->vale;
PrintBST(r->right, r->val, max_val);
}
}
//print open interval (min_val, max_val) in r1 and r2
void Print2BST(BSTNode* r1, BSTNode* r2, int min_val, int max_val)
{
if(r1 == NULL && r2 == NULL) return;
else if(r1 == NULL) PrintBST(r2, min_val, max_val); // only one tree
else if(r2 == NULL) PrintBST(r1, min_val, max_val); // only one tree
else {
//make sure r1->val < r2->val
if(r1->val > r2->val) swap(r1, r2);
if(r1->val <= min_val)//cut the left subtree of r1
Print2BST(r1->right, r2, min_val, max_val);
else if(r1->val >= max_val)//cut the right subtree of r1
Print2BST(r1->left, r2, min_val, max_val);
else if(r2->val <= min_val)//cut the left subtree of r2
Print2BST(r1, r2->right, min_val, max_val);
else if(r2->val >= max_val) //cut the right subtree of r2
Print2BST(r1, r2->left, min_val, max_val);
else {
// cut into 5 partion as following
// (min_val, r1->vale) | r1->val |
// (r1->val, r2->val) | r2->val | (r2->val, max_val)
Print2BST(r1->left, r2->left, min_val, r1->val);
cout << r1->val;
Print2BST(r1->right, r2->left, r1->val, r2->val);
cout << r2->val;
Print2BST(r1->right, r2->right, r2->val, max_val);
}
}
}
void Print2BST(BSTNode* r1, BSTNode* r2)
{
Print2BST(r1, r2, INT_MIN, INT_MAX);
} |
b***i
发帖数: 3043 | 27 good. u r hired.
【在 f*********d 的大作中提到】
: //我上个代码吧, 没有测试过, 有错误或者bug请指出。。。
: //这里假设所有节点的值都不一样, 如果存在一样的节点值, 需要一点修改。。。
: struct BSTNode {
: BSTNode* left;
: BSTNode* right;
: int val;
: }
: //print open interval (min_val, max_val) in r
: void PrintBST(BSTNode* r, int min_val, int max_val)
: {
|
P******r
发帖数: 842 | 28 能把原来的tree结构给该了吗?改成一个bst。要行的话，就可以用recursion，O(1)
【在 Y********f 的大作中提到】
: 除了recursion外只能有O(1)的extra space。有什么好的方法。
: 我的想法是用iterative方法同时in order访问两个树，比较节点大小，打印小的，然
: 后找到该节点的下一个节点。但是需要O(lgN)的space。
|
y***u
发帖数: 174 | 29 这个行么？recursive的。
我需要暂时把左子树或者右子树变成null，不然太麻烦。
void Traverse(ArrayList output, Node A, Node B){
if(A==null && B==null)
return;
else if(A==null){
output.add(B.val);
return;
}else if(B==null){
output.add(A.val);
return;
}else{
Node t1 = null, t2=null;
if(B.val>A.val){
Trav(output, A, B);
}else if(B.val < A.val){
Trav(output, B, A);
}else{
output.add(A.val);
output.add(B.val);
Traverse(output, A.left, B.left);
Traverse(output, A.right, B.right);
}
return;
}
}
void Trav(ArrayList output, Node small, Node large){
t1 = small.right;
small.right = null;
Traverse(output, small, big.left);
t2 = big.left;
big.left = null;
Traverse(output, t1, big);
small.right = t1;
big.left = t2;
}
【在 Y********f 的大作中提到】
: 除了recursion外只能有O(1)的extra space。有什么好的方法。
: 我的想法是用iterative方法同时in order访问两个树，比较节点大小，打印小的，然
: 后找到该节点的下一个节点。但是需要O(lgN)的space。
|
b***i
发帖数: 3043 | 30 你这个差一点，看看fograinwind的吧
【在 e****e 的大作中提到】
: 我来个Recursion code，欢迎指正：
: public void print(TreeNode n1, TreeNode n2) {
: if ( n1 == null && n2 == null )
: return;
: else if ( n1 == null && n2 != null )
: print(n2);
: else if ( n1 != null && n2 == null )
: print(n1);
: else {
: print(n1.left, n2.left)
|
|
|
P******r
发帖数: 842 | 31 我这个行吗？merge完了再来个inorder traversal
Node * merge(Node * r, Node * s) {
if (!r)
return s;
if (!s)
return r;
if (r->d <= s->d) {
Node * rright = r->right;
r->right = NULL;
Node * l = merge(r, s->left);
s->left = l;
return merge(rright, s);
}
else return merge(s, r);
} |
