LeetCode Q144: Binary Tree Preorder Traversal (hard)

Given a binary tree, return the preorder traversal of its nodes' values.

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

   1
    \
     2
    /
   3

return [1,2,3].

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> preorderTraversal(TreeNode* root) {
	vector<int> res;
	stack<TreeNode*> myS;
	unordered_map<TreeNode*, int> myM;
	if(root==NULL)
	return res;
	res.push_back(root->val);
	myS.push(root);
	myM[root]=2;
	while(!myS.empty()){
	TreeNode* cur=myS.top();
	if(cur==NULL){
	myS.pop();
	continue;
	}
	if(myM[cur]==2){
	myM[cur]=myM[cur]-1;
	if(cur->left!=NULL){
	myS.push(cur->left);
	myM[cur->left]=2;
	res.push_back(cur->left->val);
	}
	continue;
	}
	if(myM[cur]==1){
	myM[cur]=myM[cur]-1;
	if(cur->right!=NULL){
	myS.push(cur->right);
	myM[cur->right]=2;
	res.push_back(cur->right->val);
	}
	continue;
	}
	if(myM[cur]==0)
	myS.pop();
	}
	return res;
	}
	};

view raw Q144.cpp hosted with ❤ by GitHub

Round 2 solution:
Very similar to inorder traversal, but save element when first meet.

	/**
	* 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> preorderTraversal(TreeNode* root) {
	vector<int> res;
	if(root==NULL)
	return res;
	TreeNode* cur=NULL;
	stack<TreeNode*> myStack;
	myStack.push(root);
	res.push_back(root->val);
	cur = root->left;
	while(!myStack.empty()||cur!=NULL){
	if(cur!=NULL){
	res.push_back(cur->val);
	myStack.push(cur);
	cur = cur->left;
	}else{
	TreeNode* top = myStack.top();
	myStack.pop();
	cur = top->right;
	}
	}
	return res;
	}
	};

view raw Q144Rnd2.cpp hosted with ❤ by GitHub