二叉树的前序,中序,后续(非递归版本)

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

二叉树的非递归版本的前序中序后序在面试中也经常考,必须熟练掌握！
下面将会讲如何非递归打印二叉树的前中后序。

一、前序

思路：递归改非递归一般都要用到数据结构栈,当前节点出栈的时候打印,并有右节点先加入右节点,
后加入左节点,因为前序根左右,而栈是逆序,所以先入有节点。

void Print(TreeNode* root)
{
    
    //前序
    stack<TreeNode*> s = stack<TreeNode*>();//创建栈
    s.push(root);//头结点入栈
     入栈顺序有右压右,有左压左
    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);
        }

    }
}

二、后序

思路:与前序不同,后序我们需要两个栈进行调换,第一个栈得出的结果顺序是根右左,因为栈逆序,我们将s1栈中的数据放入s2就得到了左右根,后续操作和前序相似。

后序
    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;
    }

三、中序

代码如下:

中序
    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;
        }
    }

总结