#include <bits/stdc++.h>
using namespace std;
struct node
{
int data;
struct node *left;
struct node *right;
};
struct node * make( int x)
{
struct node *temp = (struct node*) malloc(sizeof(struct node));
temp->data = x;
temp->left = NULL;
temp->right = NULL;
return temp;
}
void print( struct node *head)
{
struct node *temp = head;
do {
cout << temp->data << " ";
temp = temp->right;
}while (temp != head);
}
void inorder( struct node *root)
{
if ( root != NULL ) {
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
return;
}
void treetolist( struct node *root, struct node **prev,struct node **head)
{
if ( root == NULL ) {
return;
}
treetolist(root->left,prev,head);
root->left = *prev;
if ( *prev == NULL )
*head = root;
else {
(*prev)->right = root;
}
struct node *rt = root->right;
(*head)->left = root;
root->right = *head;
*prev = root;
treetolist(rt,prev,head);
}
int main() {
struct node *root = make(4);
root->left = make(2);
root->left->left = make(1);
root->left->right = make(3);
root->right = make(5);
// inorder(root);
struct node *prev = NULL;
struct node *head = NULL;
treetolist(root,&prev,&head);
print(head);
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnN0cnVjdCBub2RlIAp7CglpbnQgZGF0YTsKCXN0cnVjdCBub2RlICpsZWZ0OwoJc3RydWN0IG5vZGUgKnJpZ2h0OwoJCn07CnN0cnVjdCBub2RlICogbWFrZSggaW50IHgpCnsKCXN0cnVjdCBub2RlICp0ZW1wID0gKHN0cnVjdCBub2RlKikgbWFsbG9jKHNpemVvZihzdHJ1Y3Qgbm9kZSkpOwoJdGVtcC0+ZGF0YSA9IHg7Cgl0ZW1wLT5sZWZ0ID0gTlVMTDsKCXRlbXAtPnJpZ2h0ID0gTlVMTDsKCXJldHVybiB0ZW1wOwp9Cgp2b2lkIHByaW50KCBzdHJ1Y3Qgbm9kZSAqaGVhZCkKewoJCglzdHJ1Y3Qgbm9kZSAqdGVtcCA9IGhlYWQ7CglkbyB7CgkJY291dCA8PCB0ZW1wLT5kYXRhIDw8ICIgIjsKCQl0ZW1wID0gdGVtcC0+cmlnaHQ7Cgl9d2hpbGUgKHRlbXAgIT0gaGVhZCk7CgkKfQoKdm9pZCBpbm9yZGVyKCBzdHJ1Y3Qgbm9kZSAqcm9vdCkKewoJaWYgKCByb290ICE9IE5VTEwgKSB7CgkJaW5vcmRlcihyb290LT5sZWZ0KTsKCQljb3V0IDw8IHJvb3QtPmRhdGEgPDwgIiAiOwoJCWlub3JkZXIocm9vdC0+cmlnaHQpOwoJfQoJcmV0dXJuOwp9Cgp2b2lkIHRyZWV0b2xpc3QoIHN0cnVjdCBub2RlICpyb290LCBzdHJ1Y3Qgbm9kZSAqKnByZXYsc3RydWN0IG5vZGUgKipoZWFkKQp7CgkKCWlmICggcm9vdCA9PSBOVUxMICkgewoJCXJldHVybjsKCX0KCXRyZWV0b2xpc3Qocm9vdC0+bGVmdCxwcmV2LGhlYWQpOwoJcm9vdC0+bGVmdCA9ICpwcmV2OwoJaWYgKCAqcHJldiA9PSBOVUxMICkKCSAgICpoZWFkID0gcm9vdDsKICAgIAogICAgZWxzZSB7CiAgICAJKCpwcmV2KS0+cmlnaHQgPSByb290OwogICAgfQoJCglzdHJ1Y3Qgbm9kZSAqcnQgPSByb290LT5yaWdodDsKCQoJKCpoZWFkKS0+bGVmdCA9IHJvb3Q7Cglyb290LT5yaWdodCA9ICpoZWFkOwoJKnByZXYgPSByb290OwoJdHJlZXRvbGlzdChydCxwcmV2LGhlYWQpOwoJCn0KCmludCBtYWluKCkgewoJc3RydWN0IG5vZGUgKnJvb3QgPSBtYWtlKDQpOwoJcm9vdC0+bGVmdCA9IG1ha2UoMik7Cglyb290LT5sZWZ0LT5sZWZ0ID0gbWFrZSgxKTsKCXJvb3QtPmxlZnQtPnJpZ2h0ID0gbWFrZSgzKTsKCXJvb3QtPnJpZ2h0ID0gbWFrZSg1KTsKLy8JaW5vcmRlcihyb290KTsKCXN0cnVjdCBub2RlICpwcmV2ID0gTlVMTDsKCXN0cnVjdCBub2RlICpoZWFkID0gTlVMTDsKCXRyZWV0b2xpc3Qocm9vdCwmcHJldiwmaGVhZCk7CglwcmludChoZWFkKTsKCXJldHVybiAwOwp9