一道题：2个BST，按大小顺序打印两棵树的所有节点# JobHunting - 待字闺中
Y*f
1 楼
除了recursion外只能有O(1)的extra space。有什么好的方法。
我的想法是用iterative方法同时in order访问两个树，比较节点大小，打印小的，然
后找到该节点的下一个节点。但是需要O(lgN)的space。
我的想法是用iterative方法同时in order访问两个树，比较节点大小，打印小的，然
后找到该节点的下一个节点。但是需要O(lgN)的space。
w*x
2 楼
把bst化为linked list然后再用merge sort的逻辑打印, 前提是bst化为linked list的
递归栈空间不算
【在 Y********f 的大作中提到】
: 除了recursion外只能有O(1)的extra space。有什么好的方法。
: 我的想法是用iterative方法同时in order访问两个树，比较节点大小，打印小的，然
: 后找到该节点的下一个节点。但是需要O(lgN)的space。
b*i
3 楼
可以用recursion吗？
可以就好办。
【在 Y********f 的大作中提到】
: 除了recursion外只能有O(1)的extra space。有什么好的方法。
: 我的想法是用iterative方法同时in order访问两个树，比较节点大小，打印小的，然
: 后找到该节点的下一个节点。但是需要O(lgN)的space。
可以就好办。
【在 Y********f 的大作中提到】
: 除了recursion外只能有O(1)的extra space。有什么好的方法。
: 我的想法是用iterative方法同时in order访问两个树，比较节点大小，打印小的，然
: 后找到该节点的下一个节点。但是需要O(lgN)的space。
T*7
4 楼
愿问详情
【在 b***i 的大作中提到】
: 可以用recursion吗？
: 可以就好办。
【在 b***i 的大作中提到】
: 可以用recursion吗？
: 可以就好办。
p*2
5 楼
可以用two threads吗？
w*x
6 楼
two thread也要堆栈啊
【在 p*****2 的大作中提到】
: 可以用two threads吗？
p*2
7 楼
不是有O(1)的traverse吗？
【在 w****x 的大作中提到】
:
: two thread也要堆栈啊
w*x
8 楼
没有parent怎么O(1)?
【在 p*****2 的大作中提到】
:
: 不是有O(1)的traverse吗？
C*U
9 楼
晕
我不是刚发过一个帖子么
呵呵
【在 w****x 的大作中提到】
:
: 没有parent怎么O(1)?
我不是刚发过一个帖子么
呵呵
【在 w****x 的大作中提到】
:
: 没有parent怎么O(1)?
i*e
10 楼
用Morris In-order traversal 可以实现不用栈 O(1)空间复杂度。
可是如何实现两个遍历操作之间的同步？如果用两个线程分别遍历两个BST，每遍历一
个结点难道就让这个线程sleep吗？
可是如何实现两个遍历操作之间的同步？如果用两个线程分别遍历两个BST，每遍历一
个结点难道就让这个线程sleep吗？
i*e
11 楼
用Morris In-order traversal 可以实现不用栈 O(1)空间复杂度。
可是如何实现两个遍历操作之间的同步？如果用两个线程分别遍历两个BST，每遍历一
个结点难道就让这个线程sleep吗？
可是如何实现两个遍历操作之间的同步？如果用两个线程分别遍历两个BST，每遍历一
个结点难道就让这个线程sleep吗？
i*e
12 楼
用Morris In-order traversal 可以实现不用栈 O(1)空间复杂度。
可是如何实现两个遍历操作之间的同步？如果用两个线程分别遍历两个BST，每遍历一
个结点难道就让这个线程sleep吗？
可是如何实现两个遍历操作之间的同步？如果用两个线程分别遍历两个BST，每遍历一
个结点难道就让这个线程sleep吗？
Y*f
13 楼
two thread的话仅仅要用到mutex/cond以及另外几个临时变量吧
【在 w****x 的大作中提到】
:
: 没有parent怎么O(1)?
【在 w****x 的大作中提到】
:
: 没有parent怎么O(1)?
Y*f
14 楼
只要不是recursive控制同步还是比较简单吧。
【在 i******e 的大作中提到】
: 用Morris In-order traversal 可以实现不用栈 O(1)空间复杂度。
: 可是如何实现两个遍历操作之间的同步？如果用两个线程分别遍历两个BST，每遍历一
: 个结点难道就让这个线程sleep吗？
【在 i******e 的大作中提到】
: 用Morris In-order traversal 可以实现不用栈 O(1)空间复杂度。
: 可是如何实现两个遍历操作之间的同步？如果用两个线程分别遍历两个BST，每遍历一
: 个结点难道就让这个线程sleep吗？
i*e
15 楼
是呀。这不是和producer-consumer model有点类似吗？ 当一个线程遍历了一个结点之
后block自己同时signal另一个线程遍历另一BST的下一个结点然后比较直到两棵树都遍
历完。
如果有parent指针可以实现getNextNode()函数（O(1)操作）， 可以分别对两棵BST分
别扫描， 就不需要线程同步的方法了。
你说用iterative方法需要O(lgN)的space。 为什么？
后block自己同时signal另一个线程遍历另一BST的下一个结点然后比较直到两棵树都遍
历完。
如果有parent指针可以实现getNextNode()函数（O(1)操作）， 可以分别对两棵BST分
别扫描， 就不需要线程同步的方法了。
你说用iterative方法需要O(lgN)的space。 为什么？
p*2
16 楼
还有一个办法就是实现getNext
这样单进程就可以完成。
这样单进程就可以完成。
Y*f
17 楼
iterative方法需要自己维护一个栈吧。当然上面提到的morris方法不用，但是比较复
杂，面试应该不会写这个。
【在 i******e 的大作中提到】
: 是呀。这不是和producer-consumer model有点类似吗？ 当一个线程遍历了一个结点之
: 后block自己同时signal另一个线程遍历另一BST的下一个结点然后比较直到两棵树都遍
: 历完。
: 如果有parent指针可以实现getNextNode()函数（O(1)操作）， 可以分别对两棵BST分
: 别扫描， 就不需要线程同步的方法了。
: 你说用iterative方法需要O(lgN)的space。 为什么？
杂，面试应该不会写这个。
【在 i******e 的大作中提到】
: 是呀。这不是和producer-consumer model有点类似吗？ 当一个线程遍历了一个结点之
: 后block自己同时signal另一个线程遍历另一BST的下一个结点然后比较直到两棵树都遍
: 历完。
: 如果有parent指针可以实现getNextNode()函数（O(1)操作）， 可以分别对两棵BST分
: 别扫描， 就不需要线程同步的方法了。
: 你说用iterative方法需要O(lgN)的space。 为什么？
p*2
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
19 楼
一个方案是两个线程。
另一个方案，就是看楼主的题目是不是就是要求可以用recursion，不然我说了，然后
再加上各种额外的限制不就不行了？
方法是这样的，traverse1(int seq, Node * node) 将返回node为头的从小开始第seq
个数。
main的程序写个循环什么的，分别从两个BST读入第0个数字，第1个数字什么的。然后
比较，直到最后。这样当然很浪费，每次都要从头寻找，但是要求就是这样，有什么办
法。
【在 T******7 的大作中提到】
: 愿问详情
另一个方案，就是看楼主的题目是不是就是要求可以用recursion，不然我说了，然后
再加上各种额外的限制不就不行了？
方法是这样的，traverse1(int seq, Node * node) 将返回node为头的从小开始第seq
个数。
main的程序写个循环什么的，分别从两个BST读入第0个数字，第1个数字什么的。然后
比较，直到最后。这样当然很浪费，每次都要从头寻找，但是要求就是这样，有什么办
法。
【在 T******7 的大作中提到】
: 愿问详情
g*e
20 楼
用俩个thread 或者goto语句？hoho
g*e
21 楼
用俩个thread 或者goto语句？hoho
Y*f
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;
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
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);
}
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
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
25 楼
二爷详细说说。
【在 p*****2 的大作中提到】
:
: 感觉这个code挺悬的。
【在 p*****2 的大作中提到】
:
: 感觉这个code挺悬的。
f*d
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);
}
//这里假设所有节点的值都不一样, 如果存在一样的节点值, 需要一点修改。。。
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
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)
: {
【在 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
28 楼
能把原来的tree结构给该了吗?改成一个bst。要行的话，就可以用recursion，O(1)
【在 Y********f 的大作中提到】
: 除了recursion外只能有O(1)的extra space。有什么好的方法。
: 我的想法是用iterative方法同时in order访问两个树，比较节点大小，打印小的，然
: 后找到该节点的下一个节点。但是需要O(lgN)的space。
【在 Y********f 的大作中提到】
: 除了recursion外只能有O(1)的extra space。有什么好的方法。
: 我的想法是用iterative方法同时in order访问两个树，比较节点大小，打印小的，然
: 后找到该节点的下一个节点。但是需要O(lgN)的space。
y*u
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。
我需要暂时把左子树或者右子树变成null，不然太麻烦。
void Traverse(ArrayList
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
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
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)
【在 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
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);
}
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);
}
相关阅读
申请OPT对雇主有什么要求不？找工作找的很depressed, 大牛给出出主意H1b pendnig期间不能回国是不是？ (转载)OPT 60+90天？ (转载)如果被公司派回中国工作还需要H-1B么？LA senior java developer/architect等 position问个H1B的问题刚刚网投的PDF简历，如果公司发信问我要WORD格式的签了Offer再做reference check是啥意思求推荐纽约地区H1B律师问个浮点数求和的问题G 电面 第三轮明天下午phone interview，求bless(update)J1转F1后，现在OPT，被公司问是否有J1waiver,该怎么回答？问问Sr. Java SDE 的行情请教问题，在线等！上周四有个local的面试，结束时manager说这周一会做决定面试题目的次序对发挥会有影响？5个包子求解。。。。。。 (转载)职位明说要c++ for linux的，如果没用过是不是基本没戏？