#include <iostream>
#include <vector>
using namespace std;

struct TreeNode{
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x):val(x),left(NULL),right(NULL){}
};

void inVist(vector<TreeNode*> &vec,TreeNode *T){
	if(T!=NULL){
		inVist(vec,T->left);
		vec.push_back(T);
		inVist(vec,T->right);
	}
}

TreeNode* Convert(TreeNode* pRootOfTree){
	if(pRootOfTree==NULL) return NULL;
    TreeNode *head;
	vector<TreeNode*> vec;
	inVist(vec,pRootOfTree);
	int len=vec.size();
	head=vec[0];
	for(int i=1;i<len;i++){
		vec[i]->left=vec[i-1];
		vec[i-1]->right=vec[i];
	}
	return head;
}

int main(){
	TreeNode n1(5),n2(3),n3(7),n4(2),n5(4),n6(6),n7(8);
	TreeNode *root=&n1;
	n1.left=&n2;
	n1.right=&n3;
	n2.left=&n4;
	n2.right=&n5;
	n3.left=&n6;
	n3.right=&n7;
	Convert(root);
	system("pause");
}