145. 二叉树的后序遍历

//递归
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
vector<int>v;

vector<int> postorderTraversal(TreeNode* root) {
    if(!root)
        return v;
    postorderTraversal(root->left);
    postorderTraversal(root->right);
    v.emplace_back(root->val);
    return v;
}

//迭代
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
vector<int> postorderTraversal(TreeNode* root) {
    stack<TreeNode *> s;
    vector<int> v;
    if (root != nullptr)
        s.push(root);

    while (!s.empty()) {
        auto *cur = s.top();
        s.pop();
        if (cur == nullptr) {
            v.emplace_back(s.top()->val);
            s.pop();
        } else {
            //左右根
            s.push(cur);
            s.push(nullptr);
            if(cur->right)
                s.push(cur->right);
            if(cur->left)
                s.push(cur->left);
        }
    }
    return v;
}