vector<int> preorderTraversal(TreeNode* root) {
    vector<int> res;
    if (!root)
        return res;
    stack<TreeNode *> st;
    TreeNode *p = root;
    while (p != nullptr || !st.empty()) {
        while (p != nullptr) {
            res.push_back(p->val);
            st.push(p);
            p = p->left;
        }
        if (!st.empty()) {
            p = st.top();
            st.pop();
            p = p->right;
        }
    }
    return res;
}

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> res;
    if (!root)
        return res;
    stack<TreeNode *> st;
    TreeNode *cur = root;
    while (!st.empty() || cur != NULL) {
        if (cur != NULL) {
            st.push(cur);
            cur = cur->left;
        } else if (!st.empty()) {
            cur = st.top();
            st.pop();
            res.push_back(cur->val);
            cur = cur->right;
        }
    }
    return res;
}

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> res;
    if (!root)
        return res;
    TreeNode *cur = root;
    stack<TreeNode *> st;
    while (!st.empty() || cur != NULL) {
        while (cur != NULL) {
            res.push_back(cur->val);
            st.push(cur);
            cur = cur->right;
        }
        if (!st.empty()) {
            cur = st.top();
            st.pop();
            cur = cur->left;
        }
    }
    reverse(res.begin(), res.end());
    return res;
}

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> res;
    if (!root) 
        return res;
    traverse(root, res);
    return res;    
}
void traverse(TreeNode *p, vector<int> &res) {
    if (p == NULL)
        return;
    res.push_back(p->val);
    traverse(p->left, res);
    traverse(p->right, res);
    return;
}

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> res;
    if (!root)
        return res;
    traverse(root, res);
    return res;
}
void traverse(TreeNode *root, vector<int> &res) {
    if (!root)
        return;
    traverse(root->left, res);
    res.push_back(root->val);
    traverse(root->right, res);
}

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> res;
    if (!root)
        return res;
    traverse(root, res);
    return res;
}
void traverse(TreeNode *root, vector<int> &res) {
    if (!root)
        return;
    traverse(root->left, res);
    traverse(root->right, res);
    res.push_back(root->val);
}

class Solution {
public:
    TreeNode* Convert(TreeNode* root)
    {
        if (!root)
            return NULL;
        TreeNode *l = Convert(root->left);
        TreeNode *head = l;
        if (l != NULL) {
            while (l->right) {
                l = l->right;
            }
            l->right = root;
            root->left = l;
        } else {
            head = root;
        }
        TreeNode *r = Convert(root->right);
        root->right = r;
        if (r)
            r->left = root;
        return head;
    }
};

TreeNode* Convert(TreeNode* root)
{
    if (!root)
        return NULL;
    stack<TreeNode *> st;
    TreeNode *cur = root;
    TreeNode *head = NULL;
    TreeNode *pre_node = NULL;
    while (cur || !st.empty()) {
        while (cur) {
            st.push(cur);
            cur = cur->left;
        }
        if (!st.empty()) {
            cur = st.top(); st.pop();
            if (!head) {
                head = pre_node = cur;
            } else {
                pre_node->right = cur;
                cur->left = pre_node;
                pre_node = cur;
            }
            cur = cur->right;
        }
    }
    return head;
}