二叉树非递归遍历（C++）

文章目录

前言
一、前序遍历
二、中序遍历
三、后序遍历
总结

前言

我们之前学习过用递归解决二叉树的前序，中序，后序。
下面我们将用非递归，也就是遍历的方法对二叉树进行遍历

一、前序遍历

我们要解决这个问题最重要的就是用另一个角度看待这颗树

以下面这棵树为例子

在这里插入图片描述

我们把看成为：左路节点和左路节点的右子树

借助栈来实现

我们进行遍历，前序：根右子树左子树

🌟8,3,1入栈一直到nullptr，同时我们可以进行访问，这就是根

在这里插入图片描述

🌟取栈顶1元素，访问这个元素的右子树。由于右子树为nullptr,没有节点，继续遍历

在这里插入图片描述

🌟取栈顶元素3，遍历3的右子树

在这里插入图片描述

🌟3的右子树，根6入栈。访问左子树，4入栈.

在这里插入图片描述

🌟取栈顶元素4，访问4的右子树，右子树没有节点，继续遍历。

在这里插入图片描述

🌟下面也是同样的逻辑，遍历右子树，进行入栈。取栈顶元素进行，在遍历它的右子树

代码

    vector<int> preorderTraversal(TreeNode* root) 
    {
        vector<int>v;
        stack<TreeNode*>st;
        TreeNode*cur=root;
        while(cur||st.size()!=0)
        {
            //访问左路节点
            while(cur)
            {
                v.push_back(cur->val);
                st.push(cur);
                cur=cur->left;
            }
            //取栈顶
            TreeNode*stop=st.top();
            st.pop();
            //左路节点的右子树
            cur=stop->right;
        }
        return v;

    }

注意：
结束条件：cur遍历到空节点，但是栈里面仍然有元素，我们继续进行遍历。
当cur为空，并且栈里面也为空，说明元素已经访问完了，结束

cur=stop->right;神之一手

二、中序遍历

中序遍历：左子树根右子树

中序遍历和前序遍历十分相似，唯一不同的就是访问根的时机不同。
上面讲的前序遍历，上来遇到跟我们就进行遍历。
我们在中序遍历的时候，需要先把左子树访问完了，再访问根。
我们在进行出栈的时候进行访问

vector<int> inorderTraversal(TreeNode* root) 
    {
         vector<int>v;
        stack<TreeNode*>st;
        TreeNode*cur=root;
        while(cur||st.size()!=0)
        {
            //左路节点
            while(cur)
            {
                st.push(cur);
                cur=cur->left;
            }
            //取栈顶
            TreeNode*stop=st.top();
            //栈里面取到一个节点时，一定是它的左子树访问完了
             v.push_back(stop->val);
            st.pop();
            //左路节点1的右子树
            cur=stop->right;
        }
        return v;

    }

三、后序遍历

后序遍历和前序中序类似，也需要借助栈来实现，解决本题的关键就是什么时候可以对根节点进行访问
只有右子树访问完了，我们才可以访问这个节点，那我们怎末知道右子树是否已经访问过了呢？？

新增一个节点prev，记录前一个访问的节点

我们画图来看下

🌟遍历左路节点，左路节点入栈

在这里插入图片描述

🌟取栈顶元素1，这时不能pop,因为我们不能确定右子树是否已经被访问过了。

访问它的右子树，我们发现右子树为空，我们就可以对这个节点进行访问。这个节点访问完了，出栈。
prev=1

在这里插入图片描述

🌟继续取栈顶元素3，由于3的右子树不为nullptr,需要判断3这个节点的右子树的根节点是否等于prev.
如果等于prev,说明已经访问过了。如果不等于，我们就访问3这个节点的右子树。
我么判断而得，3->right!=prev.说明3的右子树还没有被访问。
访问3的右子树。

在这里插入图片描述

🌟继续取栈顶元素6，访问它的右子树。右子树为空，可以访问6这个节点,同时出栈。同时prev更新为6
在这里插入图片描述

🌟取栈顶元素3，由于3的右子树不为nullptr,需要判断3这个节点的右子树的根节点是否等于prev.
如果等于prev,说明已经访问过了。如果不等于，我们就访问3这个节点的右子树。
经过判断，3->right==prev.说明右子树已经访问完了。我们可以访问3这个节点了。

在这里插入图片描述

🌟后面也是同样的道理。

在这里插入图片描述

总结：🌟如果这个节点右子树为空，可以访问这个节点。
🌟或者这个节点的右子树等于prev(最近访问节点)，就说明这个节点的右子树已经访问过了，可以访问这个节点。
🌟否则，访问它的右子树

代码

    vector<int> postorderTraversal(TreeNode* root) 
    {
        stack<TreeNode*>st;
        vector<int>v;
        TreeNode*cur=root;
        TreeNode*prev=nullptr;
        while(cur||!st.empty())
        {
            //左路节点入栈
            while(cur)
            {
                st.push(cur);
                cur=cur->left;
            }
            //取栈顶元素
            TreeNode*stop=st.top();
            //这里不能pop

            //栈里面取到top说明top左子树已经访问完了

            //如果右子树为nullptr可以访问这个节点
            //右子树不为nullptr,且上一个访问节点就是这个节点的右子树的根，可以访问这个节点
            if(stop->right==nullptr||stop->right==prev)
            {
                v.push_back(stop->val);
                st.pop();
                //更新上一个访问的最新节点
                prev=stop;
            }
            //否则子问题访问右子树
            else
            {
                cur=stop->right;
            }
        }
        return v;
    }