#include <iostream>
#include <string>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    /* 迭代法 前(根)序遍历 */
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stack0;
        TreeNode* cur = root;
        while (cur || stack0.size()) {
            while (cur) {
                stack0.push(cur);
                res.push_back(cur->val);
                cur = cur->left;
            }
            cur = stack0.top();
            stack0.pop();
            cur = cur->right;
        }

        return res;
    }
    /* 迭代法 中(根)序遍历 */
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stack0;
        TreeNode* cur = root;

        while (cur || stack0.size()) {
            while (cur) {
                stack0.push(cur);
                cur = cur->left;
            }

            cur = stack0.top();
            stack0.pop();
            res.push_back(cur->val);
            cur = cur->right;
        }

        return res;
    }
    /* 迭代法 后(根)序遍历 */ 
    /* 后序遍历是参考前序遍历 利用“根-右-左”的顺序代替“根-左-右”的顺序，然后进行vector转置得到*/
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stack0;
        TreeNode* cur = root;

        while (cur || stack0.size()) {
            while (cur) {
                stack0.push(cur);
                res.push_back(cur->val);
                cur = cur->right;
            }
            cur = stack0.top();
            stack0.pop();
            cur = cur->left;
        }

        reverse(res.begin(), res.end()); //头文件algorithm
        return res;
    }
};

int main()
{
    Solution sol;
    return 0;
}