//morris

vector<int> preorderTraversal(TreeNode* root) {

vector<int> ret;

TreeNode temp, p=root;

while(p){

if(!p->left) {

ret.push_back(p->val);

p=p->right;

}else{

temp=p->left;

while(temp->right && temp->right!=p){

temp=temp->right;

}

if(!temp->right){

temp->right=p;

ret.push_back(p->val);

p=p->left;

}else{

temp->right=nullptr;

p=p->right;

}

}

}

return ret;

}