145.binary-tree-postorder-traversal 二叉树的后序遍历

对比前序遍历的"中左右"，后序遍历是"左右中"，颠倒一下就是"中右左"，所以可以参照前序遍历的迭代法来写迭代遍历。

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

递归法

class Solution {
public:
    vector<int> res;
    vector<int> postorderTraversal(TreeNode* root) {
        if (root == nullptr)
            return res;
        postorderTraversal(root->left);
        postorderTraversal(root->right);
        res.push_back(root->val);
        return res;
    }
};