# My 3 solutions in c++

• ``````// recursive, it's trivial...
vector<int> v;
vector<int> inorderTraversal(TreeNode* root) {
if(!root) return v;
inorderTraversal(root->left);
v.push_back(root->val);
inorderTraversal(root->right);
return v;
}

// iterate, use stack
vector<int> inorderTraversal(TreeNode* root) {
vector<int> v;
if(!root) return v;
TreeNode* temp = root;
stack<TreeNode*> s;
while(true){
while(temp){
s.push(temp);
temp = temp->left;
}
if(s.empty()) break;
temp = s.top();
s.pop();
v.push_back(temp->val);
temp = temp->right;
}
return v;
}

// iterate, morris traversal, without stack
vector<int> inorderTraversal(TreeNode* root) {
vector<int> v;
if(!root) return v;
TreeNode* temp = root, *prev;
while(temp){
if(!temp->left){
v.push_back(temp->val);
temp = temp->right;
}else{
prev = temp->left;
while(prev->right&&(prev->right != temp))
prev = prev->right;
if(!prev->right){
prev->right = temp;
temp = temp->left;
}else{
v.push_back(temp->val);
prev->right = NULL;
temp = temp->right;
}
}
}
}``````

• Can you explain how the second solution works, please? I see you push the root to the stack first time go into the while, and set temp = temp->left. But you never used this temp before reassign it to s.top(). This code worked, but how could this be. I'm confused.

• while(temp){...} just goes to the left end, and pop S's top when it ends. S'top value is what we need at this iteration.Draw a tree may help you learn better.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.