Given a binary tree, return the postorder traversal of its nodes’ values.

For example:
Given binary tree `{1,#,2,3}`,

``````   1
\
2
/
3
``````

return `[3,2,1]`.

Note: Recursive solution is trivial, could you do it iteratively?

``````
class Solution {
public:
stack<TreeNode*> treeStack;
unordered_map<TreeNode*, int> treeTraversalMap;

bool checkNode(TreeNode* node)
{
if(treeTraversalMap.find(node) == treeTraversalMap.end()) return false;

return treeTraversalMap[node] == 1;
}

vector<int> postorderTraversal(TreeNode* root)
{
vector<int> res;
if(root)
{
treeStack.push(root);
TreeNode* ptr = root;
treeTraversalMap[root] = 0;

while(!treeStack.empty())
{
while(ptr->left)
{
ptr = ptr->left;
treeStack.push(ptr);
}

while(!ptr->right || checkNode(ptr))
{
if(!treeStack.empty())
{
ptr = treeStack.top();
if(!ptr->right || checkNode(ptr))
{
treeStack.pop();
res.push_back(ptr->val);
}
}
else
{
ptr = nullptr;
break;
}
}

if(ptr)
{
treeTraversalMap[ptr] = 1;
ptr = ptr->right;
treeStack.push(ptr);
}
}
}

return res;
}
};
``````