//
//  Solution145.cpp
//  Algorithm
//
//  Created by Pancf on 2019/12/21.
//  Copyright © 2019 Pancf. All rights reserved.
//

#include "Solution145.hpp"
#include <stack>

using std::stack;

vector<int> Solution145::postorderTraversal(TreeNode *root) {
    vector<int> rv;
    if (!root) {
        return rv;
    }
    auto cur = root;
    // last用来记录上次访问过出栈的结点
    TreeNode *last = nullptr;
    stack<TreeNode *> st;
    while (cur || !st.empty()) {
        if (cur) {
            // 访问左子树
            st.push(cur);
            cur = cur->left;
        } else {
            auto top = st.top();
            if (!top->right || last == top->right) {
                // 只有栈顶结点右子树为空或者右子树已经被访问过时，才保存栈顶节点的值，然后出栈，
                // 代表以该结点为根节点的左右子树都已经被访问过
                rv.push_back(top->val);
                last = top;
                st.pop();
            } else {
                // 右子树不为空且未被访问时
                cur = top->right;
            }
        }
    }
    return rv;
}