本文共 2730 字，大约阅读时间需要 9 分钟。

1. 题目信息

给定一个二叉树，返回它的 后序 遍历。

示例:输入: [1,null,2,3]     1    \     2    /   3 输出: [3,2,1]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

来源：力扣（LeetCode）

2. 解法

2.1 递归

class Solution {
   public:    vector
   
     postorderTraversal(TreeNode* root) {
           vector
    
      ans;        preorder(root, ans);        return ans;    }    void preorder(TreeNode* root, vector
     
       &ans)    {
           if(root == NULL)            return;        preorder(root->left, ans);        preorder(root->right, ans);        ans.push_back(root->val);    }};
     
    
   

2.2 循环，必须掌握

左右根

a. 单栈

• 先按照"根-右-左"的顺序遍历二叉树(和先序遍历有些像)，
• 然后将遍历的结果反转过来就是“左-右-根”，也就是后序遍历了

class Solution {
   public:    vector
   
     postorderTraversal(TreeNode* root) {
           vector
    
      ans;        stack
     
       stk;        while(root || !stk.empty())        {
               while(root)            {
                   stk.push(root);                ans.push_back(root->val);                root = root->right;            }            root = stk.top()->left;            stk.pop();        }        //反转遍历结果        reverse(ans.begin(),ans.end());        return ans;    }};
     
    
   

以下解法会破坏二叉树

class Solution {
   public:    vector
   
     postorderTraversal(TreeNode* root) {
           vector
    
      ans;        if(root==NULL)            return ans;        TreeNode *cur;        stack
     
       stk;        stk.push(root);        while(!stk.empty())        {
               cur = stk.top();            if(cur->left)            {
                   stk.push(cur->left);                cur->left = NULL;            }            else if(cur->right)            {
                   stk.push(cur->right);                cur->right = NULL;            }            else            {
                   ans.push_back(cur->val);                stk.pop();            }        }        return ans;    }};
     
    
   

b. 双栈解法

• stk1，模仿前序遍历的实现“反后序遍历”
• stk2，保存stk1的pop元素

class Solution {
   public:    vector
   
     postorderTraversal(TreeNode *root) {
           vector
    
      ans;        if(root == NULL) return ans;        stack
     
       stk1;        stack
      
        stk2;        stk1.push(root);        TreeNode *cur;        while(!stk1.empty())        {
               cur = stk1.top();            stk1.pop();            stk2.push(cur);            if(cur->left)                stk1.push(cur->left);            if(cur->right)                stk1.push(cur->right);        }        while(!stk2.empty())        {
               cur = stk2.top();            stk2.pop();            ans.push_back(cur->val);        }        return ans;    }};
      
     
    
   

3. 前中后序总结

转载地址：https://michael.blog.csdn.net/article/details/100546489 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！