LeetCode Q145: Binary Tree Postorder Traversal

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?

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	vector<int> postorderTraversal(TreeNode* root) {
	vector<int> res;
	unordered_map<TreeNode*, int> myM;
	stack<TreeNode*> myS;
	if(root==NULL)
	return res;
	myS.push(root);
	myM[root]=2;
	while(!myS.empty()){
	TreeNode* cur=myS.top();
	if(myM[cur]==2){
	myM[cur]=myM[cur]-1;
	if(cur->left!=NULL){
	myS.push(cur->left);
	myM[cur->left]=2;
	}
	continue;
	}
	if(myM[cur]==1){
	myM[cur]=myM[cur]-1;
	if(cur->right!=NULL){
	myS.push(cur->right);
	myM[cur->right]=2;
	}
	continue;
	}
	if(myM[cur]==0){
	res.push_back(cur->val);
	myS.pop();
	continue;
	}
	}
	}
	};

view raw Q145.cpp hosted with ❤ by GitHub

Round 2 solution:

1.1 Create an empty stack
2.1 Do following while root is not NULL
    a) Push root's right child and then root to stack.
    b) Set root as root's left child.
2.2 Pop an item from stack and set it as root.
    a) If the popped item has a right child and the right child 
       is at top of stack, then remove the right child from stack,
       push the root back and set root as root's right child.
    b) Else print root's data and set root as NULL.
2.3 Repeat steps 2.1 and 2.2 while stack is not empty.

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	vector<int> postorderTraversal(TreeNode* root) {
	vector<int> res;
	if(root==NULL)
	return res;
	stack<TreeNode*> myStack;
	myStack.push(root->right); // push both current node and its right child to stack;
	myStack.push(root);
	TreeNode* cur = root->left;
	while(!myStack.empty()){
	if(cur!=NULL){
	myStack.push(cur->right);
	myStack.push(cur);
	cur = cur->left;
	}else{
	cur = myStack.top();
	myStack.pop();
	if(cur==NULL)
	continue;
	if(cur->right!=NULL&&myStack.size()!=0&&cur->right==myStack.top()){
	myStack.pop();
	myStack.push(cur);
	cur = cur->right;
	}else{
	res.push_back(cur->val);
	cur=NULL;
	}
	}
	}
	return res;
	}
	};

view raw Q145Rnd2.cpp hosted with ❤ by GitHub