LeetCode Q94: Binary Tree Inorder Traversal

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

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

   1
    \
     2
    /
   3

return [1,3,2].

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

Solution 1 (Recursive)

	/**
	* 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:
	void helper(TreeNode* node, vector<int>& savedNodes){
	if(node->left!=NULL)
	helper(node->left, savedNodes);
	savedNodes.push_back(node->val);
	if(node->right!=NULL)
	helper(node->right, savedNodes);
	}
	vector<int> inorderTraversal(TreeNode* root) {
	vector<int> nodes;
	if(root==NULL)
	return nodes;
	helper(root, nodes);
	return nodes;
	}
	};

view raw Q94-1.cpp hosted with ❤ by GitHub

Solution 2 (Non-recursive)

	/**
	* 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> inorderTraversal(TreeNode* root) {
	vector<int> nodes;
	if(root==NULL)
	return nodes;
	stack<TreeNode*> myStack;
	myStack.push(root);
	unordered_map<TreeNode*, int> myMap;
	while(!myStack.empty()){
	TreeNode* topNode=myStack.top();
	if(topNode->left!=NULL && myMap[topNode->left]!=1){
	myStack.push(topNode->left);
	continue;
	}
	nodes.push_back(topNode->val);
	myMap[topNode]=1;
	myStack.pop();
	if(topNode->right!=NULL && myMap[topNode->right]!=1){
	myStack.push(topNode->right);
	continue;
	}
	}
	return nodes;
	}
	};

view raw Q94-2.cpp hosted with ❤ by GitHub

Round 2 solution:

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

view raw Q94Rnd2.cpp hosted with ❤ by GitHub