bobobo老师好，我想问您有关于后序遍历的非递归写法

来源：6-9 二分搜索树前序遍历的非递归实现

江景又妍和

2019-05-14

老师，看了您的视频，我对前序遍历的非递归写法有了清晰的理解。然后我自己想动手写一下后序遍历的非递归写法，但是，我对递归转非递归还是不是很明白，所以没写出来。

然后我就参考了您在第一课推荐的github上c++版本的代码库，对于中序遍历的非递归写法我明白了，但是他写的后序遍历，我通过调试能看懂他的运行顺序，但是不明白这个是怎么样的一个思想，是如何写出来的？
所以我想问bobobo老师两个问题
1.麻烦老师可不可简单的说一下后序遍历的非递归写法的思想呢
2.老师我觉得递归转非递归我还不是很清晰，所以您觉得我问题出在哪呢？

谢谢老师，然后我附上github上c++版的后序非递归算法实现

 void postOrderNR() {
        std::stack<Node<T> *> stack;
        Node<T> *cur = root;
        Node<T> *temp;
        while (cur != nullptr || !stack.empty()) {
            while (cur != nullptr) {
                stack.push(cur);
                cur = cur->left;
            }
            if (!stack.empty()) {
                cur = stack.top();
                if (cur->right == temp || cur->right == nullptr){
                    std::cout << cur->e << " ";
                    stack.pop();
                    temp = cur;
                    cur = nullptr;
                }else {
                    cur = cur->right;
                }

            }
        }
        std::cout << std::endl;
    }

写回答

3回答

liuyubobobo

2019-05-15

已采纳

首先，我来说一下递归转非递归的问题。其实，递归转非递归，非常简单，本质就是自己创造一个栈，来模拟系统栈的调用。所以，你只需要想明白，递归函数里都保存了什么状态，压进栈里就好了。

我不知道你是否购买了我的《玩转算法面试》课程，在那个课程中，我以二叉树的前中后序遍历为例，说明了这个递归转非递归的过程。如果你没有购买，也可以直接去看github上的代码(C++)：

https://github.com/liuyubobobo/Play-with-Algorithm-Interview/tree/master/06-Stack-and-Queue/Course%20Code%20(C%2B%2B)/03-Non-Recursive-Implementation-of-a-Recursive-Algorithm

但是，要注意的是，通常数据结构教材中，对于二叉树的中序和后序的非递归遍历的逻辑，本质不完全是在模拟系统栈。所以，在我看来，不是一个标准的递归转非递归的思路。如果一定要理解其中的逻辑，只能case by case的去理解。我认为不能通过一般教材里的二叉树前中后序的非递归遍历逻辑，提炼出一般的递归转非递归的方法。再强调一次：通用的递归转非递归的方法，是使用你自己的栈，模拟系统栈调用。

下面我们来具体看一下这段逻辑是怎么回事儿。

核心是：对于后序遍历来说，每个节点，必须先遍历完了他的左右孩子，才能打印输出这个节点。

关键是怎么确保对每个节点，遍历完了他的左右孩子：

void postOrderNR() {

    std::stack<Node<T> *> stack;
    Node<T> *cur = root;
    Node<T> *temp; // temp用来存储上一个后序遍历访问的节点
    
    while (cur != nullptr || !stack.empty()) {
        // 先疯狂往左走，
        while (cur != nullptr) {
            stack.push(cur);
            cur = cur->left;
        }
        
        // 左边走不下去了，开始回退
        if (!stack.empty()) {
             // 现在，对于栈顶的cur，我们可以保证他的左孩子遍历完了
             // 因为左边走不下去了嘛
             cur = stack.top();
             
             // 下面，我们看，对于这个cur，要不要遍历右边？
             // 有两种情况，不需要遍历右边
             // 一种情况是，根本就没有右子树（cur->right == nullptr）
             // 另一种情况是，右边已经遍历过了。
             // 根据后序遍历的性质，如果右边已经遍历过了，一定是上一次遍历的结果
             // 所以存在了temp中
             if (cur->right == temp || cur->right == nullptr){
                 
                 // 满足这两个条件之一，我们就可以遍历cur了
                 std::cout << cur->e << " ";
                 stack.pop();
                 temp = cur; // 注意，要把cur放在temp中，也就是现在最后遍历的是cur
                 
                 // 其实这句话是争端逻辑最tricky的地方，这里cur必须置空
                 // 只有置空，在下一轮主循环中，cue才会不被再次压入栈，而是取新的栈顶元素
                 cur = nullptr;
             }else {
             
                 // 不满足这两个条件，cur往右走
                 cur = cur->right;
             }
        }
    }
    std::cout << std::endl;
}

其实，对于后序遍历的非递归，还有很多别的写法。但基本上，核心都是：每个节点，必须确保先遍历完了他的左右孩子，才能打印输出这个节点。

还是要再强调一次，这些非递归的思路，在我看来不是普遍的递归转非递归的思路。所以你要理解其中的逻辑，需要去专门看其中的逻辑。不要试图从这个代码中抽象出通用的递归转非递归的思路。通用的递归转非递归的方法，是使用你自己的栈，模拟系统栈调用。我在《玩转算法面试》课程中有讲。

https://github.com/liuyubobobo/Play-with-Algorithm-Interview/tree/master/06-Stack-and-Queue/Course%20Code%20(C%2B%2B)/03-Non-Recursive-Implementation-of-a-Recursive-Algorithm

这个代码对应的思路，在我看来是通用的：）

继续加油！：）

liuyubobobo

江景又妍和

大赞！这种方法最酷的地方在，可以统一前中后序三种遍历的非递归代码，使得这三种遍历的非递归代码，就像递归代码一样，只改动一个顺序就好了：）继续加油！：）

2019-05-23

共3条回复

yao0446022

2019-08-25

bobo老师，我有一个能简易写出非递归的中序遍历和后序遍历的方法，只是因为最近在老家，周边没有电脑，不能确定自己的想法对不对，所以想和大家讨论一下。

从非递归写出前序遍历的本质上来看，每次处理栈顶的元素，首先先打印栈顶节点的值，然后分别将栈顶节点的右孩子和左孩子节点，再将栈顶节点出栈，如此循环直到栈空。

如果用同样的方式来处理中序，那么每次就是先将栈顶节点的右孩子入栈，再将打印节点的操作入栈，再将左孩子入栈，剩下的操作和之前的一样。那么问题就在于如何将打印操作入栈？我的想法是封装新对象t，也就是在栈中存放的不是节点，而是新对象t，在对象t中存放如何操作栈顶元素的操作，比如说操作a就是操作节点，操作b就是打印操作，每次也是操作栈顶元素。