Preorder, inorder, follow-up of binary tree (non recursive version)

Tips ： When the article is finished , Directories can be generated automatically , How to generate it, please refer to the help document on the right

---

Preface

The pre order, middle order and post order of the non recursive version of the binary tree are also often tested in the interview , Must be proficient in ！
Next, we will talk about how to print the first, middle and last sequence of binary tree non recursively .

One 、 Before the order

Ideas ： Data structure stack is generally used to change recursion to non recursion , Print when the current node is out of the stack , And a right node is added to the right node first ,
Then add the left node , Because the antecedent root is about , The stack is in reverse order , So first enter the node .

void Print(TreeNode* root)
{
    
    // Before the order 
    stack<TreeNode*> s = stack<TreeNode*>();// Create a stack 
    s.push(root);// Head node stack 
      The order of stacking is right pressing right , There is left pressure left 
    while (!s.empty())
    {
    
        TreeNode* cur = s.top();
        s.pop();
        cout << to_string(cur->val)+"" ;
        if (cur->right)
        {
    
            s.push(cur->right);
        }
        if (cur->left)
        {
    
            s.push(cur->left);
        }

    }
}

Two 、 In the following order

Ideas : Different from the previous sequence , In the following sequence, we need two stacks to exchange , The result order of the first stack is root right left , Because the stack is in reverse order , We will s1 Put the data in the stack s2 You get left and right , Subsequent operations are similar to those in the previous sequence .

 In the following order 
    stack<TreeNode*> s1 = stack<TreeNode*>();
    stack<TreeNode*> s2 = stack<TreeNode*>();
    s1.push(root);
    while (!s1.empty())
    {
    
        TreeNode* cur = s1.top();
        s1.pop();
        s2.push(cur);
        if (cur->left)
        {
    
            s1.push(cur->left);
        }
        if (cur->right)
        {
    
            s1.push(cur->right);
        }
    }
    while (!s2.empty())
    {
    
        TreeNode* cur = s2.top();
        s2.pop();
        cout << cur->val << endl;
    }

3、 ... and 、 Middle preface

The code is as follows :

 Middle preface 
    stack<TreeNode*> t = stack<TreeNode*>();
    TreeNode* cur = root;
    while (!t.empty() || cur!=nullptr)
    {
    

        if (cur!= nullptr)
        {
    
            t.push(cur);
            cur = cur->left;
        }
        else
        {
    
            cur = t.top();
            t.pop();
            cout << cur->val << endl;
            cur = cur->right;
        }
    }

summary