// 前序
class Solution {
public:

    //前序，中左右
    //非递归遍历，加入中,出栈，加入res,同时按照右左顺序将节点加入栈
    
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> sk;
        if (!root) return res;
        sk.push(root);
        while(!sk.empty()) {
            TreeNode* x = sk.top();
            sk.pop();
            res.push_back(x->val);
            if (x->right) sk.push(x->right);
            if (x->left) sk.push(x->left);
        }
        return res;
    }
};

// 后序

class Solution {
public:
    // 左右中
    // 其实是变化前序的逆序列
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> sk;
        if (!root) return res;
        sk.push(root);
        while (!sk.empty()) {
            TreeNode* x = sk.top();
            sk.pop();
            res.push_back(x->val);
            if (x->left) sk.push(x->left);
            if (x->right) sk.push(x->right);
        }
        reverse(res.begin(),res.end());
        return res;
    }
};

// 中序
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        if (!root) return res;
        TreeNode* cur = root;
        while (cur) {
            TreeNode* mostRight = cur->left;
            if (!mostRight) {
                res.push_back(cur->val);
                cur = cur->right;
            }else {
                while (mostRight->right && mostRight->right != cur) {
                    mostRight = mostRight->right;
                }
                if (mostRight->right == nullptr) {
                    mostRight->right = cur;
                    cur = cur->left;
                }else {
                    mostRight->right = nullptr;
                    res.push_back(cur->val);
                    cur = cur->right;
                }
            }
        }
        return res;
    }
};