# A traditional solution based on stack. the idea can be used to post-order traversal

• Expect for preorder traversal, the other two problems meet the question that how we get the parent node?Same process with preorder, but i use a tricky, insert a node without children. Absolutely，postorder traversal can also use the tricky(of course, there is another very excellent solution)

the code cost 3ms:

vector<int> inorderTraversal(TreeNode *root) {
vector<int> v;
if(!root) return v;

stack<TreeNode*> s;

s.push(root);
while(!s.empty())
{
TreeNode* r = s.top();
s.pop();
if(!r->left && !r->right)
{
v.push_back(r->val);
continue;
}
if(r->right) s.push(r->right);
s.push(new TreeNode(r->val)); // here....
if(r->left) s.push(r->left);
}
return v;
}

but this may cost too much memory, update to this(8ms):

vector<int> inorderTraversal(TreeNode *root) {
vector<int> v;
if(!root) return v;

typedef pair<TreeNode*, int> elem;
stack<elem> s;

s.push(elem(root, 0));
while(!s.empty())
{
elem e = s.top();
s.pop();
TreeNode* r = e.first;
if(!r || (!r->left && !r->right))
{
v.push_back(r ? r->val : e.second);
continue;
}
if(r->right) s.push(elem(r->right, 0));
s.push(elem(NULL, r->val));
if(r->left) s.push(elem(r->left, 0));
}
return v;
}

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