二叉树的后序遍历-C++两种方式-牛客BM25

一、题目

给定一个二叉树，返回他的后序遍历的序列。后序遍历是值按照 左节点->右节点->根节点 的顺序的遍历。

数据范围：二叉树的节点数量满足0≤n≤100 ，二叉树节点的值满足 1≤val≤100 ，树的各节点的值各不相同

二、递归方式

运行结果：

代码：

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

三、非递归方式（借助两个辅助栈）

运行结果：

代码：

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ans;
        if(root == NULL) return ans;
        stack<TreeNode*> st1;
        stack<TreeNode*> st2; //st2保存的就是中序遍历顺序序列
        TreeNode* p = root;
        st1.push(p);
        while(!st1.empty()){
            p = st1.top();
            st2.push(p);
            st1.pop();
            if(p->left){
                st1.push(p->left);
            }
            if(p->right){
                st1.push(p->right);
            }
        }
        while(!st2.empty()){
            ans.emplace_back(st2.top()->val);
            st2.pop();
        }
        return ans;
    }
};