题目：
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?
解题思路：
后序遍历的非递归实现与前序遍历和中序遍历的非递归不同，对于根节点，必须当其右孩子都访问完毕后才能访问，所以当根节点出栈时，要根据标志位判断是否为第一次出栈，如果是，则将其标志位置为FALSE，然后再次入栈，先访问其右孩子，当某个节点出栈时且其标志位为false，说明该节点为第二次出栈，即表示其右孩子都已处理完毕，可以访问当前节点了
实现代码：
#include <iostream>
#include <vector>
#include <stack>
using namespace std; /**
Given a binary tree, return the postorder traversal of its nodes' values.
*/ struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
}; void addNode(TreeNode* &root, int val)
{
if(root == NULL)
{
TreeNode *node = new TreeNode(val);
root = node;
}
else if(root->val < val)
{
addNode(root->right, val);
}
else if(root->val > val)
{
addNode(root->left, val);
}
} void printTree(TreeNode *root)
{
if(root)
{
cout<<root->val<<" ";
printTree(root->left);
printTree(root->right);
}
}
struct Node
{
TreeNode *treeNode;
bool isFirst;
}; class Solution {
public:
vector<int> postorderTraversal(TreeNode *root) {
vector<int> ivec;
if(root)
{
stack<Node*> istack;
TreeNode *p = root;
while(!istack.empty() || p)
{
while(p)
{
Node *tmpNode = new Node();
tmpNode->treeNode = p;
tmpNode->isFirst = true;
istack.push(tmpNode);
p = p->left;
}
if(!istack.empty())
{
Node *node = istack.top();
istack.pop();
if(node->isFirst)//第一次出栈，
{
node->isFirst = false;
istack.push(node);
p = node->treeNode->right;
}
else//表示其右孩子都已经访问了，可以访问当前节点了
{
ivec.push_back(node->treeNode->val);
}
} } }
return ivec; }
};
int main(void)
{
TreeNode *root = new TreeNode();
addNode(root, );
addNode(root, );
addNode(root, );
addNode(root, );
printTree(root);
cout<<endl; Solution solution;
vector<int> v = solution.postorderTraversal(root);
vector<int>::iterator iter;
for(iter = v.begin(); iter != v.end(); ++iter)
cout<<*iter<<" ";
cout<<endl; return ;
}