## 代码实现

#include <iostream>
using std::cout;
using std::cin;
using std::endl;

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

class Solution {
public:
TreeNode* Convert(TreeNode* pRootOfTree)
{
TreeNode* p = pRootOfTree;
TreeNode* pl;
TreeNode* pr;
if( p != NULL ) {
pl = Convert(p->left);
pr = Convert(p->right);
p->right= pr;
if(pr){
pr->left = p;
}
while(pl&&pl->right){
pl = pl->right;
}
if(pl)
pl->right= p;
p->left= pl;
while(p->left){
p = p->left;
}
}
return p;
}
};

int main(){
TreeNode* p1 = new TreeNode(1);
TreeNode* p2 = new TreeNode(2);
TreeNode* p3 = new TreeNode(3);
TreeNode* p4 = new TreeNode(4);
TreeNode* p5 = new TreeNode(5);
TreeNode* p6 = new TreeNode(6);
TreeNode* p7 = new TreeNode(7);

p4->left = p2;
p4->right= p6;
p2->left = p1;
p2->right= p3;

p6->left= p5;
p6->right= p7;

Solution s;

TreeNode* p = s.Convert(p4);
while(p->right){
cout<<p->val<<" ";
p = p->right;
}
cout<<p->val<<" ";
cout<<"\n";
while(p->left){
cout<<p->val<<" ";
p = p->left;
}
cout<<p->val<<" ";

}