//前序遍历
class Solution{
public:
    vector<int> preorderTraversal(TreeNode *root){
        vector<int> res;
        stack<TreeNode*> s;
        TreeNode* p = root;

        if(!p) return res;
        s.push(p);
        while(!s.empty()){
            p = s.top();
            s.pop();
            res.push_back(p->val);

            if(p->right) s.push(p->right);
            if(p->left) s.push(p->left);
        }
        return res;
    }
};
//中序遍历
class Solution{
public:
    vector<int> inorderTraversal(TreeNode* root){
        vector<int> res;
        stack<TreeNode*> s;
        TreeNode* p = root;

        while(p || !s.empty()){
            if(p != nullptr){
                s.push(p);
                p = p->left;
            }else{
                p = s.top();
                res.push_back(p->val);
                s.pop();
                p = p-> right();
            }
        }

        return res;
    }
};
//后序遍历
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        TreeNode* p = root;
        if (!p)
            return res;

        stack<pair<TreeNode*, int>> s;
        s.push(make_pair(p, 0));
        while (!s.empty()) {
            int times = s.top().second;
            TreeNode* p = s.top().first;
            s.pop();
            if (times == 0) {
                s.push(make_pair(p, 1));
                if (p->right)
                    s.push(make_pair(p->right, 0));
                if (p->left)
                    s.push(make_pair(p->left, 0));
            }
            if (times == 1) {
                res.push_back(p->val);
            }
        }
        return res;
    }
};
//层级遍历
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if(root == nullptr) return res;

        TreeNode* p = root;
        queue<TreeNode*> current,next;
        vector<int> levelElem;

        current.push(p);
        while(!current.empty()){
            while(!current.empty()){
                p = current.front();
                current.pop();
                levelElem.push_back(p->val);

                if(p->left) next.push(p->left);
                if(p->right) next.push(p->right);
            }
            res.push_back(levelElem);
            levelElem.clear();
            swap(current,next);
        }
        return res;
    }
};