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

递归写法已经烂大街，这里继续只讨论堆栈的方法;

思路：首先前序遍历是：根-左-右，后续遍历是：左-右-根，发现没有，假如我将前序遍历先反转下：右-左-根，只要再次把左右节点的顺序给调换即可！好嘛，说了这么多，代码上面如何实现上面的操作呢？首先你得知道前序遍历的非递归写法，这里我直接贴上代码：

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> res;
        if(root == nullptr) return res;
        st.push(root);
        while(!st.empty()){
            TreeNode* cur = st.top();
            st.pop();
            res.push_back(cur->val);
            if(cur->right) st.push(cur->right);
            if(cur->left) st.push(cur->left);
        }
        return res;
    }
};

• 1. 通过上面的分析，我们要想通过谦虚遍历实现后序遍历，可以先做一个这样的前序遍历：根 - 右- 左；然后直接反转即可
• 2. 观察上面的前序遍历代码，我们只需要调换这两行代码的顺序即可：if(cur->right) st.push(cur->right);if(cur->left) st.push(cur->left);,上面的是先遍历右节点，然后是左节点，注意啊，因为堆栈的先进后出特性，所有你想实现左右，反而要右左放进去。
• 3. 此时我们想要实右左，那么只要按照左右的顺序放进去即可。最终这样遍历得到的顺序是反转的后序遍历，再次反转我们的数组即可

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        if(root == nullptr) return res;
        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty()){
            TreeNode* cur = st.top();
            st.pop();
            res.push_back(cur->val);
            if(cur->left) st.push(cur->left);
            if(cur->right) st.push(cur->right);
        }
        reverse(res.begin(), res.end());
        return res;
    }
};