【二叉树进阶】二叉树的前中后序遍历（非递归迭代实现）

YIN_尹

发布于 2024-01-23 14:20:08

1670

发布于 2024-01-23 14:20:08

文章被收录于专栏：YIN_尹的博客YIN_尹的博客

1. 二叉树的前序遍历

题目链接: link

不用递归，用迭代算法如何实现对二叉树的前序遍历？

最终放到一个vector里面返回。

1.1 思路分析

前序遍历的非递归呢我们可以这样来搞：

题目中给的二叉树比较简单，下面通过这样一棵二叉树给大家讲解：

对它进行非递归的前序遍历，它是这样搞的：前序遍历是根、左子树、右子树所以首先从根结点开始，顺着访问左子树：8、3、1 然后现在还有谁没访问？ 🆗，是1的左子树、3的左子树，和8的左子树。所以下面倒着访问1、3、8的左子树就行了。所以非递归的前序遍历是这样处理的： 他把一棵二叉树分为两个部分：

左路结点
左路结点的右子树

对于每一棵左子树，也是同样划分为这两个部分进行处理。

那现在问题来了，如何倒着去处理左路结点的右子树？

那此时我们就可以借助一个栈来搞。

还是以这棵树为例，从根结点8开始，依次访问左路结点8，3，1。 在访问过程中除了将他们放到要返回的vector里面，再把左路结点放到栈里面

然后： 依次取栈顶元素（1 3 8 ），访问它们的右子树。 那这是不是就是一个前序遍历的顺序啊。那如何处理它们的右子树啊？ 🆗，这是不是一个子问题啊。首先1出栈，访问1的右子树，那为空，就直接结束。

然后再取栈顶元素3，访问它的右子树。所以我们此时就要循环上去，从3的右子树的根结点6开始，进行同样的处理。 首先访问3的右子树的左路结点并入栈

然后4、6出栈，先后处理4、6的右子树，对于子树同样循环上去进行处理。后续也是如此，我这里就不继续往下画了。大家如果还不是特别理解可以继续往下画完。

1.2 AC代码

那我们来写一下代码：

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ret;
        stack<TreeNode*> st;
        TreeNode* cur=root;

        //循环结束条件：
        //1.cur不为空表示还有树没有访问
        //2.栈不为空表示还有结点的右子树没处理
        while(cur||!st.empty())
        {
            //遍历左路结点并入栈
            while(cur)
            {
                ret.push_back(cur->val);
                st.push(cur);
                cur=cur->left;
            }
            
            //取栈顶元素并访问它的右子树
            TreeNode* top=st.top();
            st.pop();

            //怎么处理它的右子树？
            //子问题，把cur置成右子树的根，上去重新进行循环即可
            cur=top->right;
        }
        return ret;
    }
};

当然不止我们这里讲的这一种方法，不过我们这个后面比较方便往中序和后序的方向上修改。

2. 二叉树的中序遍历

题目链接: link

接下来我们就来看一下二叉树中序遍历的非递归如何实现

2.1 思路分析

其实大体的思路还是跟上一道题的差不多，最后写出来跟上一题的代码也基本一样，其中一句代码换一下位置就行了

那我们这里还是，每一棵树都把它分成左路结点和右子树

回忆一下上一题我们的前序是怎么走的：、

我们是在左路结点入栈的时候就把它放到要返回的vector里面，因为这就符合前序遍历的顺序。那现在是中序遍历，中序是先访问左子树，然后再访问根 所以我们先把左路结点入栈，但是不放进vector里面。

一直走到1的左子树为空然后停止入栈，那这时就可以认为1的左子树是空已经遍历过了。然后出栈里面的元素（从栈里面取出一个左路结点的时候，就意味着它的左子树已经访问过了），第一个出的是1，那此时遇到1我们要把它放到vector里面吗？ 🆗，这时就要放了，因为1的左子树访问过后，就要访问根了（左子树、根、右子树）

那1的根访问完，然后要访问柚子是，这里1的右是空，但是其它测试用例不一定是空啊。那要访问右子树怎么办？是不是还是让它循环上去，从当前左路结点的右子树的根开始进行同样的处理。 当然这里1的右是空，所以下面就直接取栈顶下一个元素了，那就是3

然后处理3的右子树。循环上去，从根结点6开始进行同样的处理左路结点6，4入栈

然后4出栈，处理4的左，左为空。接着6出栈，处理6的左

那对于6的左，就是循环上去，对7这棵子树进同样的处理 7入栈，左为空，不再继续入了。接着7出栈，放进vector。

接着处理7的左。后续也是一样，8出栈，然后处理8的左大家看现在的访问顺序是不是中序的

后面我就不画了。

2.2 AC代码

那代码很简单，跟上一题相比，是不是就是入vector的时机变了啊

前序是入栈的时候就放到vector里面，中序是出栈的时候在放到vector里面

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ret;
        stack<TreeNode*> st;
        TreeNode* cur=root;

        while(cur||!st.empty())
        {
            //遍历左路结点并入栈
            while(cur)
            {
                st.push(cur);
                cur=cur->left;
            }
            
            //取栈顶元素的时候再入vector
            TreeNode* top=st.top();
            st.pop();
            ret.push_back(top->val);

            //处理右子树
            //子问题，把cur置成右子树的根，上去重新进行循环即可
            cur=top->right;
        }
        return ret;
    }
};

3. 二叉树的后序遍历

题目链接: link

那后序遍历的非递归又如何实现呢？这里提供两种思路

3.1 思路1

思路1呢是这样的：

大家想前序是根、左子树、右子树。后序是左子树、右子树、根。那如果我们实现一个根、右子树、左子树的遍历，然后把得到的vector逆置一下是不是就是后序遍历的结果啊。那怎么能够得到一个根、右子树、左子树的遍历呢？ 🆗，我们把前序遍历的代码修改一下，访问完根之后先访问右子树、在访问左子树不就行了嘛。

3.2 思路1AC

很简单，修改两句代码的事：

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ret;
        stack<TreeNode*> st;
        TreeNode* cur=root;

        //循环结束条件：
        //1.cur不为空表示还有树没有访问
        //2.栈不为空表示还有结点的左子树没处理
        while(cur||!st.empty())
        {
            //遍历右路结点并入栈同时入vector
            while(cur)
            {
                ret.push_back(cur->val);
                st.push(cur);
                cur=cur->right;
            }
            
            //取栈顶元素并访问它的左子树
            TreeNode* top=st.top();
            st.pop();

            //怎么处理它的左子树？
            //子问题，把cur置成左子树的根，上去重新进行循环即可
            cur=top->left;
        }
        reverse(ret.begin(),ret.end());
        return ret;
    }
};

3.3 思路2

那如果我们就想像上面的前序中序那样按照正确的顺序去实现遍历呢？而不是用刚才这种取巧的方法：

后序遍历是左子树、右子树、根；而中序遍历是左子树、根、右子树所以，后序遍历前面的操作和中序是一样的：还是先让左路结点入栈

然后对于栈顶的元素我们可以直接让它入vector然后pop掉嘛。 中序我们就是这样做的，因为从栈里面取出一个左路结点的时候，就意味着它的左子树已经访问过了，然后中序的话该访问根了，而把栈顶元素放到vector里面然后pop掉就相当于访问根结点。但是我们后序就不能直接这样了，因为后序要在右子树访问完之后再去访问根

那怎么办？

其实很简单，加一个判断就行了。能不能直接pop，然后放到vector里面，其实要看情况：

大家看对于1这种情况我们可不可以直接访问，是不是可以啊，因为1的右子树为空。那如果是6这种情况呢？就不可以了，因为它的右子树不为空，所以要先访问右子树7。那7访问完把7pop掉之后回到6这里，这次可以访问6了吗？那这时就可以了，因为6的右子树访问过了。所以两种情况我们可以直接访问根：

右子树为空如果右子树不为空，就不能值访问根，要先访问右子树
右子树已经访问过了

那右子树为空，这很好判断，但是如何判断一个结点的右子树是否已经访问过了呢？ 🆗，我们可以定义一个prev指针，每次处理完一个结点pop掉之后，把这个结点赋值给prev。然后我们就可以通过prev判断某个结点前面被访问的结点是不是它的右子树 prev==top.right

那思路呢就是这样的，我们来写一下代码：

3.4 思路2AC

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ret;
        stack<TreeNode*> st;
        TreeNode* cur=root;

        TreeNode* prev=nullptr;
        while(cur||!st.empty())
        {
            //遍历左路结点并入栈
            while(cur)
            {
                st.push(cur);
                cur=cur->left;
            }
            
            //取到栈顶结点的时候它的左子树已经访问过了
            TreeNode* top=st.top();

            //如果当前取到的栈顶结点的右子树为空或者右子树已经被访问过了，就可以访问根结点
            if(top->right==nullptr||prev==top->right)
            {
                st.pop();
                ret.push_back(top->val);

                //记录prev
                prev=top;
            }
            //否则，就需要先处理右子树
            else
            {
                cur=top->right;
            }
        }
        return ret;
    }
};