题解 | #二叉树的后序遍历#

一.题目介绍

题目意思很简单就是给定出一个二叉树，返回他的后序遍历的序列。

二.算法一(递归)

首先我们需要了解什么是二叉树的后序遍历：按照访问根左子树-右子树-节点的方式遍历这棵树，而在访问左子树和右子树的时候我们按照同样的方式遍历，直到遍历整棵树。我们对先序遍历进行进一步分析：

/*
若二叉树是空树，则什么都不做；否则：
(1)访问左子树
(2)先序遍历右子树
(3)先序遍历节点
*/
void preorder(TreeNode* t){
        if(t!=NULL) return ;
        xian(t->left);//先序遍历左子树
        xian(t->right);//先序遍历右子树 
        visit(t);//假设访问函数visit已经访问过来，其中包含看对结点t的各种操作，如打印td
}

我们对先序遍历有了进一步的了解，那么整个题目就简单了，直接看代码:

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

时间复杂度：$O(n)O(n)$ 对于每一位进行递归操作

空间复杂度：$O(n)O(n)$需要对每一个节点的记录，所以空间复杂度是$O(n)O(n)$

三.算法(栈)

在迭代算法中，思路演变成，每到一个节点A，就应该立即访问它的左子树。因为，每棵子树都先访问其左子树。对节点的左右子树来说，也一定是先访问左子树。在A的两棵子树中，遍历完左子树后，再遍历右子树，然后遍历节点。因此，在遍历节点前，要将左子树压入栈。

栈S;
p= root;
while(p || S不空){
    while(p){
        p的左子树入S;
        访问p节点;
        p = p的右子树;
    }
    p = S栈顶弹出;
}

下面是完整代码：

class Solution {
public:
     void postorder(TreeNode* root,vector<int>& v) {
        stack<TreeNode*> S;
        TreeNode* rt = root;
        while(rt || S.size()){
            while(rt){
                S.push(rt->left);//左子树入栈
                v.push_back(rt->val);//访问节点
                rt=rt->right;//遍历右节点
            }
            rt=S.top();S.pop();
        }
        reverse(v.begin(),v.end());
    }
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int>tr;
        postorder(root,tr);
        return tr;
    }
};

时间复杂度：$O(n)O(n)$ 对于每一位进行访问

空间复杂度：$O(n)O(n)$需要对每一个节点的记录，所以空间复杂度是$O(n)O(n)$