花式遍历二叉树

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

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

/*
struct Command{
    //    flag     false 遍历其子节点，   true 访问当前节点
    bool flag;
    TreeNode* node;
    Command(bool flag, TreeNode* node) : flag(flag), node(node){}
};

void preOrder(TreeNode* root){
    if(!root) return ;

    stack<Command> sta;
    sta.push(Command(false, root));
    while(!sta.empty()){
        Command com = sta.top();
        sta.pop();
        if(com.flag)
            // 访问当前节点
            cout << com.node->val << ' ';
        else {
            // 后序
            if(com.node->right) sta.push(Command(fal***.node->right));
            // 中序
            if(com.node->left) sta.push(Command(fal***.node->left));
            // 前序
            sta.push(Command(true, com.node));
        }
    }
}
*/

void preOrder(TreeNode* root){
    if(!root) return ;

    //   false 遍历其子节点，   true 访问当前节点
    stack<pair<bool, TreeNode*>> sta;
    sta.push({false, root});

    while(!sta.empty()){
        pair<bool, TreeNode*> tem = sta.top();
        sta.pop();
        if(tem.first)
            // 访问当前节点
            cout << tem.second->val << ' ';
        else {
            // 后序 sta.push({true, tem.second});
            if(tem.second->right) sta.push({false, tem.second->right});
            // 中序 sta.push({true, tem.second});
            if(tem.second->left) sta.push({false, tem.second->left});
            // 前序
            sta.push({true, tem.second});
        }
    }
}



/*
void preOrder(TreeNode* root){
    if(!root) return ;
    /*
    // 递归版本， 简单
    cout<<root->val<<' ';
    preOrder(root->left);
    preOrder(root->right);
    /

    stack<TreeNode*> sta;
    TreeNode* cur = root;
    while(cur || sta.size()){
        // 访问当前节点，并压到栈里
        if(cur){
            sta.push(cur);
            cout<<cur->val<<' ';
            cur = cur->left;
        }else{
            // 当前为空时，弹出最后一个访问其右子树
            cur = sta.top();
            sta.pop();
            cur = cur->right;
        }
    }

    /*
    // 先压右子树，后压左子树
    stack<TreeNode*> sta;
    sta.push(root);
    while(sta.size()){
        root = sta.top();
        cout<<root->val<<' ';
        sta.pop();
        if(root->right) sta.push(root->right);
        if(root->left) sta.push(root->left);
    }
    /
    cout<<endl;
}
*/

void inOrder(TreeNode* root){
    if(!root) return ;
    /*
    // 递归版本， 简单
    inOrder(root->left);
    cout<<root->val<<' ';
    inOrder(root->right);
    */
    /*
    stack<TreeNode*> sta;
    TreeNode* cur = root;
    while(cur || sta.size()){
        // 把当前节点以及其左子树并压到栈里
        while(cur){
            sta.push(cur);
            cur = cur->left;
        }
        // 当前为空时，弹出最后一个访问，并访问其右子树
        cur = sta.top();
        cout<<cur->val<<' ';
        sta.pop();
        cur = cur->right;
    }*/
    // Morris遍历 中序
    // 把为空的右指针尽量用上，降低空间复杂度
    while(root){
        if(root->left){
            TreeNode* tem = root->left;
            while(tem->right && tem->right != root)
                tem = tem->right;
            // 还没有加过链接时，加上链接，方便回溯
            if(!tem->right){
                tem->right = root;
                root = root->left;
                continue;
            }
            // 已经回溯过，删除链接，恢复树的原状，并访问根节点
            tem->right = NULL;
        }
        // 访问当前节点
        cout<<root->val<<' ';
        root = root->right;
    }
    cout<<endl;
}

void postOrder(TreeNode* root){
    if(!root) return ;
    /*
    // 递归版本， 简单
    postOrder(root->left);
    postOrder(root->right);
    cout<<root->val<<' ';
    */

    stack<TreeNode*> sta;
    TreeNode* cur = root;
    TreeNode* pre = NULL;
    while(cur){
        sta.push(cur);
        cur = cur->left;
    }
    while(sta.size()){
        cur = sta.top();
        // 没有右子树，或者前一个访问的节点为其右子树
        if( !cur->right || cur->right== pre){
            cout<<cur->val<<' ';
            pre = cur;
            sta.pop();
        }else{
            cur = cur->right;
            while(cur){
                sta.push(cur);
                cur = cur->left;
            }
        }
    }
    /*
    // 两个栈， 采用前序的思想 根右左 然后经过另外一个栈，变成左右根
    stack<TreeNode*> sta;
    stack<TreeNode*> stb;
    sta.push(root);
    while(sta.size()){
        root = sta.top();
        stb.push(root);
        sta.pop();
        if(root->left) sta.push(root->left);
        if(root->right) sta.push(root->right);
    }
    while(stb.size()){
        cout<<stb.top()->val<<' ';
        stb.pop();
    }
    */
    /*
    // 左神，一个栈，然后判断
    stack<TreeNode*> sta;
    TreeNode* pre = NULL;
    sta.push(root);
    while(sta.size()){
        root = sta.top();
        if(root->left && root->left != pre && root->right != pre)
            sta.push(root->left);
        else if(root->right && root->right != pre)
            sta.push(root->right);
        else {
            cout<<root->val<<' ';
            pre = root;
            sta.pop();
        }
    }*/
    /*
    // 先加右子树再加左子树的骚操作
    stack<TreeNode*> sta;
    TreeNode* pre = NULL;
    sta.push(root);
    while(sta.size()){
        root = sta.top();
        if( (!root->left && !root->right) || (pre && root->left == pre || root->right == pre)){
            cout<<root->val<<' ';
            pre = root;
            sta.pop();
        }else{
            if(root->right) sta.push(root->right);
            if(root->left) sta.push(root->left);
        }
    }
    */
    cout<<endl;
}

void levelOrder(TreeNode* root){
    if(!root) return ;
    queue<TreeNode*> que;
    que.push(root);
    // 层次遍历，最简单
    while(que.size()){
        int len = que.size();
        while(len--){
            TreeNode* cur = que.front();
            que.pop();
            cout<<cur->val<<' ';
            if(cur->left)que.push(cur->left);
            if(cur->right)que.push(cur->right);
        }
    }
    cout<<endl;
}

int main(){
    TreeNode* root = new TreeNode(5);
    root->left = new TreeNode(3);
    root->right = new TreeNode(6);
    root->left->right = new TreeNode(7);
    root->right->left = new TreeNode(10);
    root->right->right = new TreeNode(13);

    preOrder(root);

    return 0;
}