vector<int> res//保存遍历结果;

前序遍历

递归版

void preOrder(TreeNode* root)
{
    if(root==NULL) return;
    res.push_back(root->val);
    preOrder(root->left);
    preOrder(root->right);
}

非递归版

TreeNode* cur=root;
stack<TreeNode*> stk;
while(cur!=NULL || stk.size())
{
    while(cur!=NULL)
    {
        res.push_back(cur->val);
        stk.push(cur);
        cur=cur->left;
    }
    TreeNode* p=stk.top();
    stk.pop();
    cur=p->right;
}

中序遍历

递归版

void inOrder(TreeNode* root)
{
    if(root==NULL) return;
    inOrder(root->left);
    res.push_back(root->val);
    inOrder(root->right);
}

非递归版

TreeNode* cur=root;
stack<TreeNode*> stk;
while(cur!=NULL || stk.size())
{
    while(cur!=NULL)
    {
        stk.push(cur);
        cur=cur->left;
    }
    TreeNode* p=stk.top();
    stk.pop();
    res.push_back(p->val);
    cur=p->right;
}

后序遍历

递归版

void postOrder(TreeNode* root)
{
    if(root==NULL) return;
    postOrder(root->left);
    postOrder(root->right);
    res.push_back(root->val);
}

非递归版

按左-右-根顺序遍历

TreeNode* cur=root;
stack<TreeNode*> stk;
unordered_set<TreeNode*> st;
while(cur!=NULL || stk.size())
{
    while(cur!=NULL)
    {
        stk.push(cur);
        cur=cur->left;
    }
    TreeNode* p=stk.top();
    if(st.count(p)==0)
    {
        st.insert(p);
        cur=p->right;
    }
    else
    {
        res.push_back(p->val);
        stk.pop();
    }
}

按根-右-左逆序遍历，将结果转置

TreeNode* cur=root;
stack<TreeNode*> stk;
while(cur!=NULL || stk.size())
{
    while(cur!=NULL)
    {
        res.push_back(cur->val);
        stk.push(cur);
        cur=cur->right;
    }
    TreeNode* p=stk.top();
    stk.pop();
    cur=p->left;
}
reverse(res.begin(),res.end());

层序遍历

非递归版

vector<int> getVal(vector<TreeNode*>& level)
    {
        vector<int> res;
        for(auto x:level)
            res.push_back(x->val);
        return res;
    }
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if(root==NULL) return res;
        vector<TreeNode*> level;
        level.push_back(root);
        res.push_back(getVal(level));
        while(level.size())
        {
            vector<TreeNode*> nextLevel;
            for(auto x:level)
            {
                if(x->left!=NULL)
                    nextLevel.push_back(x->left);
                if(x->right!=NULL)
                    nextLevel.push_back(x->right);
            }
            if(nextLevel.size())
                res.push_back(getVal(nextLevel));

            level=nextLevel;
        }
        return res;

    }