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
     
       postorder(treeNode*root){ 8      vector
      
        res; 9      postordertraversal(root,res);10      return res;11 }12       13 void postorderTraversal(TreeNode *root,vector
       
         &res){14     if(root==NULL) return;    15     postorderTraversal(root->left);16     postorderTraversal(root->right);17     res.push_back(root->val);18 }
       
      
     

2、非递归方法一

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

vector
     
       postorderTraversal(TreeNode *root){    vector
      
        res;    if(root==NULL) return res;    stack
       
         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
     
       postorderTraversal(TreeNode *root){        vector
      
        res;        if(root==NULL) return res;        stack
       
         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;      }