Nova2358
BAN USERThe right solution, already tested.
Idea, inorder travel two binary trees at the same time, and output the smaller one.
void print_two_binary_trees(Node* root1, Node *root2){
bool done = false;
Node *cursor1 = root1, *cursor2= root2;
stack<Node*> s1,s2;
while(!done) {
if(cursor1 != NULL && cursor2 != NULL) {
s1.push(cursor1);
cursor1 = cursor1->left;
s2.push(cursor2);
cursor2 = cursor2->left;
}
else if(cursor1 != NULL && cursor2 == NULL) {
s1.push(cursor1);
cursor1 = cursor1->left;
}
else if(cursor1 == NULL && cursor2 != NULL) {
s2.push(cursor2);
cursor2 = cursor2->left;
}
else if(cursor1 == NULL && cursor2 == NULL) {
if(!s1.empty() && s2.empty()) {
cursor1 = s1.top();
s1.pop();
cout << cursor1->data<<" ";
cursor1 = cursor1->right;
}
else if(s1.empty() && !s2.empty()) {
cursor2 = s2.top();
s2.pop();
cout << cursor2->data<<" ";
cursor2 = cursor2->right;
}
else if(!s1.empty() && !s2.empty()) {
if(s1.top()->data <= s2.top()->data) {
cursor1 = s1.top();
s1.pop();
cout << cursor1->data<<" ";
cursor1 = cursor1->right;
}
else {
cursor2 = s2.top();
s2.pop();
cout << cursor2->data<<" ";
cursor2 = cursor2->right;
}
}
else {
done = true;
}
}
}
}
P.S
Inorder travel one tree will output the elements in one tree in ascending order
void stack_inorder_visit(Node *root){
bool done = false;
stack<Node*> s;
Node* cursor = root;
while(!done) {
if(cursor != NULL)
{
s.push(cursor); //place pointer to node on the stack
//before traversing the node's left subtree
cursor = cursor->left; //traverse the left subtree
}
else //backtrack from the empty subtree and
//visit the node at the top of the stack;
//however, if the stack is empty, you are
//done
{
if (!s.empty())
{
cursor = s.top();
s.pop();
cout << cursor->data<<" ";
cursor = cursor->right;
}
else
done = true;
}
}
}
This question can be solved by using just one traverse of the binary tree.
The idea is, do a whatever order of travel, if it is the kth node we are traveling, then replace the previously selected node with probability 1/k.
This uses the idea of selecting a random node from a linkedlist where you don't know how long it is.
- Nova2358 July 12, 2012