1、遞迴法
直接上程式碼：
//recursion
class Solution1 {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ret;
postHelper(ret,root);
return ret;
}
private:
void postHelper(vector<int>& ret,TreeNode* root)
{
if(root==NULL)return;
postHelper(ret,root->left);
postHelper(ret,root->right);
ret.push_back(root->val);
};
2、迭代法
迭代法使用一個棧來儲存當前不需要訪問的節點。不過，不同於中序遍歷與前序遍歷，在後序遍歷中每一個節點需要一個標誌位，來標識當前節點的左右子樹是否被訪問。因為在後序遍歷中，只有一個節點的左右子樹被訪問後它才能被訪問。因此，壓入棧中的資料型別需要是一個pair<TreeNode*,int>，其中用1來表示當前節點的左右子樹正被訪問，當再次訪問到此節點時可以訪問此節點；用0表示當前節點的左右子樹未被訪問，再次訪問到此節點時需要首先訪問此節點的左右子樹。程式碼如下：
//iteration
if(root==NULL)return ret;
stack<pair<TreeNode*,int>> st;
st.push(make_pair(root,0));
while(!st.empty())
TreeNode *curr=st.top().first;
if(st.top().second==1)
ret.push_back(curr->val);
st.pop();
else
st.top().second=1;
if(curr->right)st.push(make_pair(curr->right,0));
if(curr->left)st.push(make_pair(curr->left,0));
3、迭代法：按照根、右、左的順序訪問然後取反
這種方法就是按照根、右、左的順序訪問，然後將結果取反即可。後序遍歷的順序是左、右、根。這種方法就可以在前序遍歷的基礎上修改即可。程式碼如下：
class Solution3 {
stack<TreeNode*> st;
st.push(root);
TreeNode *curr=st.top();
if(curr->left)st.push(curr->left);
if(curr->right)st.push(curr->right);
reverse(ret.begin(),ret.end());
在按照根、右、左的順序遍歷時，每個節點訪問一遍，最後將結果取反時，每個節點也訪問一遍，因此節點的總訪問次數和方法2相同。
4、Morris方法
後序遍歷的Morris方法思路比較難。但整體上還是一樣的，對原來的二叉樹的修改也是一樣的，不同的是訪問的順序。而在後序遍歷中，訪問時比較麻煩。下面是整個演算法的工作過程;
首先建立一個臨時節點dump，令其左兒子是root。並且還需要一個子過程，就是倒序輸出某兩個節點之間路徑上的各個節點。
步驟：
當前節點設定為臨時節點dump。
（1）如果當前節點的左兒子為空，則將其右兒子作為當前節點；
（2）如果當前節點的左兒子非空，在當前節點的左子樹中找到當前節點在中序遍歷下的前驅節點；
a) 如果前驅節點的右孩子為空，將它的右兒子設定為當前節點。當前節點更新為當前節點的左兒子；
b) 如果前驅節點的右兒子為當前節點，將它的右孩子重新設為空。倒序輸出從當前節點的左兒子到該前驅節點這條路徑上的所有節點。當前節點更新為當前節點的右兒子；
（3）重複以上（1）（2）直到當前節點為空。
程式碼如下：
//morris
class Solution4 {
TreeNode *dump=new TreeNode(0);
dump->left=root;
TreeNode *curr=dump;
TreeNode *pre;
while(curr)
if(curr->left==NULL)
curr=curr->right;
pre=curr->left;
while(pre->right&&pre->right!=curr)
pre=pre->right;
if(pre->right==NULL)
pre->right=curr;
curr=curr->left;
reverseAddNodes(curr->left,pre,ret);
pre->right=NULL;
void reverseAddNodes(TreeNode *begin,TreeNode *end,vector<int>& ret)
reverseNodes(begin,end);
TreeNode *curr=end;
while(true)
if(curr==begin)break;
reverseNodes(end,begin);
void reverseNodes(TreeNode *begin,TreeNode *end)
TreeNode *pre=begin;
TreeNode *curr=pre->right;
TreeNode *post;
while(pre!=end)
post=curr->right;
curr->right=pre;
pre=curr;
curr=post;
1、遞迴法
直接上程式碼：
//recursion
class Solution1 {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ret;
postHelper(ret,root);
return ret;
}
private:
void postHelper(vector<int>& ret,TreeNode* root)
{
if(root==NULL)return;
postHelper(ret,root->left);
postHelper(ret,root->right);
ret.push_back(root->val);
}
};
2、迭代法
迭代法使用一個棧來儲存當前不需要訪問的節點。不過，不同於中序遍歷與前序遍歷，在後序遍歷中每一個節點需要一個標誌位，來標識當前節點的左右子樹是否被訪問。因為在後序遍歷中，只有一個節點的左右子樹被訪問後它才能被訪問。因此，壓入棧中的資料型別需要是一個pair<TreeNode*,int>，其中用1來表示當前節點的左右子樹正被訪問，當再次訪問到此節點時可以訪問此節點；用0表示當前節點的左右子樹未被訪問，再次訪問到此節點時需要首先訪問此節點的左右子樹。程式碼如下：
//iteration
class Solution1 {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ret;
if(root==NULL)return ret;
stack<pair<TreeNode*,int>> st;
st.push(make_pair(root,0));
while(!st.empty())
{
TreeNode *curr=st.top().first;
if(st.top().second==1)
{
ret.push_back(curr->val);
st.pop();
}
else
{
st.top().second=1;
if(curr->right)st.push(make_pair(curr->right,0));
if(curr->left)st.push(make_pair(curr->left,0));
}
}
return ret;
}
}
3、迭代法：按照根、右、左的順序訪問然後取反
這種方法就是按照根、右、左的順序訪問，然後將結果取反即可。後序遍歷的順序是左、右、根。這種方法就可以在前序遍歷的基礎上修改即可。程式碼如下：
class Solution3 {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ret;
if(root==NULL)return ret;
stack<TreeNode*> st;
st.push(root);
while(!st.empty())
{
TreeNode *curr=st.top();
st.pop();
if(curr->left)st.push(curr->left);
if(curr->right)st.push(curr->right);
ret.push_back(curr->val);
}
reverse(ret.begin(),ret.end());
return ret;
}
};
在按照根、右、左的順序遍歷時，每個節點訪問一遍，最後將結果取反時，每個節點也訪問一遍，因此節點的總訪問次數和方法2相同。
4、Morris方法
後序遍歷的Morris方法思路比較難。但整體上還是一樣的，對原來的二叉樹的修改也是一樣的，不同的是訪問的順序。而在後序遍歷中，訪問時比較麻煩。下面是整個演算法的工作過程;
首先建立一個臨時節點dump，令其左兒子是root。並且還需要一個子過程，就是倒序輸出某兩個節點之間路徑上的各個節點。
步驟：
當前節點設定為臨時節點dump。
（1）如果當前節點的左兒子為空，則將其右兒子作為當前節點；
（2）如果當前節點的左兒子非空，在當前節點的左子樹中找到當前節點在中序遍歷下的前驅節點；
a) 如果前驅節點的右孩子為空，將它的右兒子設定為當前節點。當前節點更新為當前節點的左兒子；
b) 如果前驅節點的右兒子為當前節點，將它的右孩子重新設為空。倒序輸出從當前節點的左兒子到該前驅節點這條路徑上的所有節點。當前節點更新為當前節點的右兒子；
（3）重複以上（1）（2）直到當前節點為空。
程式碼如下：
//morris
class Solution4 {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ret;
TreeNode *dump=new TreeNode(0);
dump->left=root;
TreeNode *curr=dump;
TreeNode *pre;
while(curr)
{
if(curr->left==NULL)
{
curr=curr->right;
}
else
{
pre=curr->left;
while(pre->right&&pre->right!=curr)
pre=pre->right;
if(pre->right==NULL)
{
pre->right=curr;
curr=curr->left;
}
else
{
reverseAddNodes(curr->left,pre,ret);
pre->right=NULL;
curr=curr->right;
}
}
}
return ret;
}
private:
void reverseAddNodes(TreeNode *begin,TreeNode *end,vector<int>& ret)
{
reverseNodes(begin,end);
TreeNode *curr=end;
while(true)
{
ret.push_back(curr->val);
if(curr==begin)break;
curr=curr->right;
}
reverseNodes(end,begin);
}
void reverseNodes(TreeNode *begin,TreeNode *end)
{
TreeNode *pre=begin;
TreeNode *curr=pre->right;
TreeNode *post;
while(pre!=end)
{
post=curr->right;
curr->right=pre;
pre=curr;
curr=post;
}
}
}