二叉树的迭代遍历

反正暴力不拿offer的，复习举一反三的迭代遍历，对于树，一定要有对局部节点和整体树的思考。有空复习莫里斯遍历

struct TreeNode
{
    /* data */
    int val;
    TreeNode* left;
    TreeNode* right;
};
//前序的模拟有两种，1.先存左子树然后弹出找右子树 2.往栈里放的时候就先放右 再放左 按栈顶弹出左右
//前序 中 左  右
vector<int> preOrderIterationBTree(TreeNode* head){
    vector<int> res;
    stack<TreeNode*> s;
    TreeNode* node = head;
    //s.push(head);
    while(node!=nullptr || !s.empty()){
        //栈不为空且节点不null，栈里存放所有左子树节点
        while(node!=nullptr){
            res.push_back(node->val);//记录操作
            s.push(node);
            node = node->left;
        }
        //左节点存放完毕，取出栈顶节点，回到上一个中节点，
        node = s.top();
        s.pop();
        node = node->right;
    }
    return res;

}
// 中 左 右输出， 先压右 再压左 那么栈输出就是 左 右 输出
vector<int> preOrderIterationBTree2(TreeNode* head){
    vector<int> res;
    stack<TreeNode*> s;
    TreeNode* node = head;
    s.push(node);
    while(!s.empty()){
        node = s.top();
        s.pop();
        res.push_back(node->val);//操作记录
        if(node->right != nullptr){
            s.push(node->right);
        }
        if(node->left != nullptr){
            s.push(node->left);
        }
    }
    return res;

}


//中序，左 中 右
vector<int> inOrderIterationBTree(TreeNode* head){
    vector<int> res;
    stack<TreeNode*> s;
    TreeNode* node = head;
    //s.push(head);
    while(node!=nullptr || !s.empty()){
        //栈不为空且节点不null，栈里存放所有左子树节点
        while(node!=nullptr){
            s.push(node);
            node = node->left;
        }
        //左节点存放完毕，取出栈顶节点，回到上一个中节点，这时候存数据，以左中右顺序存val，遍历顺序
        node = s.top();
        s.pop();
        res.push_back(node->val);//记录操作
        node = node->right;
        
        //可以优化
        /* if(node != nullptr){
             node = node->right;
            }
        */
    }
    return res;

}

//后序，顺序是左 右 中
//与前序相反的，前序是中 左 右， 转化为 中 右 左，先压右子树再压左子树
//倒序打印，重要的是思路，在脑中的模拟比较复杂，面对树一定要有对节点和整体的思考
//用s1 作为 中 右 左 遍历操作的栈，用s2存遍历过程中的节点，最后输出就是 左 右 中
vector<int> postOrderIterationBTree(TreeNode* head){
    vector<int> res;
    stack<TreeNode*> s1;
    stack<TreeNode*> s2;
    TreeNode* node = head;
    s1.push(node);
    while(!s1.empty()){
        node = s1.top();
        s1.pop();
        s2.push(node);//这次的操作记录 直接存进去

        if(node->left != nullptr){
            s1.push(node->left);
        }
        if(node ->right != nullptr){
            s1.push(node->right);
        }

    }

    while(!s2.empty()){
        TreeNode* temp = s2.top();
        s2.pop();
        res.push_back(temp->val);
    }
    return res
}