# 4ms C++ solution with std::stack

• I use a stack to replace the recursion. During the iterations, each treenode is given a state. State being 0 means we need to traverse its left child and state being 1 means we have traversed its left and now need to traverse itself and its right child.

``````class Solution {
struct traverseNode
{
TreeNode* Node;
int State; // 0: need to traverse left child; 1: need to traverse right child
traverseNode(TreeNode* pNode, int state) : Node(pNode), State(state) { }
~traverseNode() { }
};

public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans = vector<int>();
if (!root) return ans;
stack<traverseNode*> stk;
stk.push(new traverseNode(root, 0));

while (!stk.empty())
{
traverseNode* pnode = stk.top();
if (pnode->State == 0) // has not traversed left child
{
if (pnode->Node->left) // has left child
{
pnode->State = 1;
stk.push(new traverseNode(pnode->Node->left, 0));
}
else // has no left child
{
ans.push_back(pnode->Node->val);
stk.pop();
if (pnode->Node->right) // has right child
{
stk.push(new traverseNode(pnode->Node->right, 0));
}
delete pnode;
}
}
else // has traversed left child
{
ans.push_back(pnode->Node->val);
stk.pop();
if (pnode->Node->right) // has right child
{
stk.push(new traverseNode(pnode->Node->right, 0));
}
delete pnode;
}
}
return ans;
}
};
``````

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