對于二叉樹的非遞歸周遊（非常好記的三種方式）

顯然，我們需要用一個stack來模拟遞歸時的函數調用。對于三種周遊，我們都使用push目前節點->push左子樹->pop左子樹->push右子樹->pop右子樹的方式。但是cout時機會有所不同。

對于前序周遊來說，每次通路到一個節點就cout；

對于中序周遊來說，每次将右子節點進棧時，把目前節點cout；

對于後序周遊來說，每次pop的時候cout。

另外我們還需要一個last_pop指針來存放上一個pop出去的節點。

如果目前節點的左右節點都不是上一個pop的節點，那麼我們将左子節點入棧；

如果目前節點的左節點是上一個pop的節點，但右節點不是，那麼就把右子節點入棧；

否則的話，就需要讓目前節點出棧。

大緻思路就是這樣，俗話說Talk is cheap, let's coding. 直接上代碼，注意三種周遊的代碼總體結構都是完全一樣的，隻是cout的時機有所不同。

前序周遊的非遞歸版本

void preorder_traversal_iteratively(TreeNode* root)
{
	if (root == 0)
		return;
	stack<TreeNode*> s;
	s.push(root);
	cout << root->val << ' '; // visit root
	TreeNode* last_pop = root;
	while (!s.empty())
	{
		TreeNode* top = s.top();
		if (top->left != NULL && top->left != last_pop && top->right != last_pop) // push_left
		{
			s.push(top->left);
			cout << top->left->val << ' '; // visit top->left
		}
		else if (top->right != NULL && top->right != last_pop && (top->left == 0 || top->left == last_pop)) // push_right
		{
			s.push(top->right);
			cout << top->right->val << ' '; // visit top->right
		}
		else // pop
		{
			s.pop();
			last_pop = top;
		}
	}
}
           

中序周遊的非遞歸版本

void inorder_traversal_iteratively(TreeNode* root)
{
	if (root == 0)
		return;
	stack<TreeNode*> s;
	s.push(root);
	TreeNode* last_pop = root;
	while (!s.empty())
	{
		TreeNode* top = s.top();
		if (top->left != 0 && top->left != last_pop && top->right != last_pop) // push_left
		{
			s.push(top->left);
		}
		else if (top->right != 0 && top->right != last_pop && (top->left == 0 || top->left == last_pop)) // push_right
		{
			s.push(top->right);
			cout << top->val << ' '; // visit top
		}
		else // pop
		{
			s.pop();
			last_pop = top;
			if (top->right == 0)
				cout << top->val << ' '; // visit top
		}
	}
}
           

後序周遊的非遞歸版本

void postorder_traversal_iteratively(TreeNode* root)
{
	if (root == 0)
		return;
	stack<TreeNode*> s;
	s.push(root);
	TreeNode* last_pop = root;
	while (!s.empty())
	{
		TreeNode* top = s.top();
		if (top->left != 0 && top->left != last_pop && top->right != last_pop) // push_left
		{
			s.push(top->left);
		}
		else if (top->right != 0 && top->right != last_pop && (top->left == 0 || top->left == last_pop)) // push_right
		{
			s.push(top->right);
		}
		else // pop
		{
			s.pop();
			last_pop = top;
			cout << top->val << ' '; // visit top
		}
	}
}