求树的后序遍历（binary-tree-postorder）

1、递归

 1 struct TreeNode{
 2     TreeNode *left;
 3     TreeNode *right;
 4     int val;
 5     TreeNode(int x):val(x),left(NULL),right(NULL){}
 6 }
 7 vector<int> postorder(treeNode*root){
 8      vector<int> res;
 9      postordertraversal(root,res);
10      return res;
11 }
12       
13 void postorderTraversal(TreeNode *root,vector<int> &res){
14     if(root==NULL) return;    
15     postorderTraversal(root->left);
16     postorderTraversal(root->right);
17     res.push_back(root->val);
18 }

2、非递归方法一

使用一个辅助栈存放待访问的树节点，一个辅助节点pre记录前一个访问节点。当栈顶元素的左右孩子节点为空或者上一个访问节点是栈顶节点的孩子节点时，访问该节点，并将其从栈顶弹出。

vector<int> postorderTraversal(TreeNode *root){
    vector<int> res;
    if(root==NULL) return res;
    stack<TreeNode *> s;
    s.push(root);
    TreeNode *cur,*pre=NULL;
    while(!s.empty()){
        cur=s.top();
        if((cur->left==NULL&&cur->right==NULL) ||  ((pre!=NULL)&&(pre==cur->left||pre==cur->right))){
            res.push_back(cur->val);
            s.pop();
            pre=cur;
            continue;
         }
         if(cur->right!=NULL) s.push(cur->right);
         if(cur->left!=NULL) s.push(cue->left);
    }
    return res;
}

3、非递归方法二

先求出树的根->右->左遍历序列，然后将其翻转即得到树的后序遍历序列

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