二叉树的后序遍历

解法1：逆置法

 class Solution {
 public:
     vector<int> postorderTraversal(TreeNode* root) 
     {
         stack<TreeNode*> s;
         vector<int> ret;
         if (root == NULL)
             return ret;
         while (!s.empty() || root)
         {
             while (root)
             {
                 ret.push_back(root->val);
                 s.emplace(root);
                 root = root->right;
             }
             root = s.top();
             s.pop();
             root = root->left;
         }
         reverse(ret.begin(), ret.end());
         return ret;
     }
 };

法2：先序遍历的正统迭代写法

 class Solution {
 public:
     vector<int> postorderTraversal(TreeNode* root) 
     {
         stack<TreeNode*> s;
         vector<int> ret;
         TreeNode* prev = NULL;
         if (root == NULL)
             return ret;
         while (!s.empty() || root)
         {
             //将当前根节点压入栈中
             while (root)
             {
                 s.emplace(root);
                 root = root->left;
             }
             root = s.top();
             //如果当前根节点的右子树为空，那么当前树的后序结构为左根
             if (root->right == NULL || root->right == prev)//防止右子树被重复遍历
             {
                 s.pop();
                 ret.push_back(root->val);
                 prev = root;
                 root = NULL;
             }
             else
             {
                 //说明右子树不为空，要对右子树进行遍历
                 root = root->right;
             }


         }
         return ret;
     }
 };

解法3：递归法

 class Solution {
 public:
     vector<int> postorderTraversal(TreeNode* root) 
     {
         vector<int> ret;
           DFS(ret,root);
         return ret;
     }
     void DFS(vector<int>& ret,TreeNode* root)
     {
        if(!root)
        return ;
        DFS(ret,root->left);
        DFS(ret,root->right);
        ret.push_back(root->val);
     }
 };

解法4：颜色标记法

 class Solution {
 public:
     vector<int> postorderTraversal(TreeNode* root)
     {
         vector<int> ret;
         stack<pair<string, TreeNode*>> s;
         if (root == NULL)
             return ret;
         s.push({"white",root});
         while (!s.empty())
         {
             pair<string,TreeNode*> temp=s.top();
             s.pop();
             if (temp.second == NULL)
                 continue;
             if (temp.first == "white")
             {
                 if (temp.second->right == NULL && temp.second->left == NULL)
                 {
                     s.push({ "grey",temp.second });
                 }
                 else
                 {
                     temp.first = "grey";
                     s.push(temp);
                     s.push({ "white", temp.second->right });
                     s.push({ "white", temp.second->left });
                 }
             }
             else
             {
                 ret.push_back(temp.second->val);
             }
         }
         return ret;
     }
 };

颜色标记法解释看中序遍历中的颜色标记解法
总结：
迭代遍历的模板

while( 栈非空 || p 非空)
{
if( p 非空)
{

}
else
{

}
}