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

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

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int>ans;
        stack<TreeNode *> s; // 栈，模拟递归
        while (root != NULL || !s.empty()) {
            if (root != NULL) {   //1.遍历左子树
                s.push(root);
                root = root->left;
            } else {
                root = s.top();
                ans.push_back(root->val);
                //2.访问节点
                s.pop();            // 将访问过的节点从栈中删除
                root = root->right; //3.遍历右子树
            }
        }
        return ans;
    }
};
int main()
{
    TreeNode* root = new(TreeNode);
    TreeNode* node2 = new(TreeNode);
    TreeNode* node3 = new(TreeNode);

    root->left = nullptr;
    root->right = node2;
    root->val = 1;

    node2->left = node3;
    node2->right = nullptr;
    node2->val = 2;

    node3->left = nullptr;
    node3->right = nullptr;
    node3->val = 3;

    Solution obj;
    vector<int> ans = obj.inorderTraversal(root);
    for(int i = 0; i < ans.size(); ++i) {
        cout<<ans[i]<<" ";
    }
    cout<<endl;
    return 0;
}