对于二叉树的三种遍历方式，它们的难易程度是不一样的，最简单的是先序遍历，其次是中序遍历，最难的是后序遍历方式。但是最难的后序遍历方式，却可以通过最简单的先序遍历方式的变形实现，然后把遍历的结果逆序一下就搞定了。哈哈，物极必反啊！

先看一个最简单的后序的遍历方法的实现，利用先序遍历方式的变形，然后逆序

vector
     
       PostOrder(TreeNode *root){	vector
      
        result;	stack
       
         s;	const TreeNode* cur = root;	if(cur != NULL)		s.push(cur);	while(!s.empty())	{		cur = s.top();		s.pop();		result.push_back(cur->val);		if(cur->left)			s.push(cur->left);		if(cur->right)			s.push(cur->right);	}	reverse(result.begin(), result.end());	return result;}
       
      
     

　　其中用到了一个std中的reverse函数，下面对这个函数做一个简单的说明：

这个函数的头文件为：

#include 
     
          // std::reverse
     

　　这个函数对vector逆序的方法就是把vector的begin()和end()作为两个参数传递进去就OK了

 

真正的后续遍历还是比较不容易的，因为除了利用栈之外，还得用一个标记记住当前这个根节点的左右孩子是否已经遍历完了，如果左右都已经遍历完了，那就可以遍历当前的结点了，如果没有遍历完，还必须让该根节点的右孩子和左孩子依次入栈。

使用的标记方法就是：对于当前的根节点，如果它的子树已经遍历完成，在这个当前结点的前一个当前结点，要么是它的左孩子（没有右子树），要么是它的右孩子。所以如果前一个遍历的结点是它的左孩子或者右孩子时，就说明这个根节点的子树都已经遍历完成了。

1.取栈顶元素为当前结点	如果当前结点没有孩子或者有孩子但是孩子（左或者右）刚刚被访问过		访问这个当前结点		更新上一个访问结点为当前的结点		做一次弹栈操作	如果有孩子并且孩子（左或者右）都不是上一个被访问的结点		把右孩子压栈，把左孩子压栈2.重复1的过程，直到栈为空，结束

　　后序遍历代码实现：

vector
     
       PostOrder(TreeNode *root){	const TreeNode *cur = NULL;	const TreeNode *pre = NULL;	stack
      
        s;	vector
       
         result;		cur = root;	if(cur != NULL)		s.push(cur);	while(!s.empty())	{		cur = s.top();		if((cur->left ==NULL && cur->right == NULL) ||			(pre != NULL && (cur->right == pre || cur->left == pre)))		{			result.push_back(cur->val);			pre = cur;			s.pop();		}		else		{			if(cur->right != NULL)				s.push(cur->right);			if(cur->left != NULL)				s.push(cur->left);		}	}//while	return result;}