bobobo老师好，我想问您有关于后序遍历的非递归写法
老师，看了您的视频，我对前序遍历的非递归写法有了清晰的理解。然后我自己想动手写一下后序遍历的非递归写法，但是，我对递归转非递归还是不是很明白，所以没写出来。
然后我就参考了您在第一课推荐的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回答
首先，我来说一下递归转非递归的问题。其实，递归转非递归，非常简单，本质就是自己创造一个栈，来模拟系统栈的调用。所以，你只需要想明白，递归函数里都保存了什么状态，压进栈里就好了。
我不知道你是否购买了我的《玩转算法面试》课程，在那个课程中，我以二叉树的前中后序遍历为例，说明了这个递归转非递归的过程。如果你没有购买，也可以直接去看github上的代码(C++)：
但是，要注意的是，通常数据结构教材中，对于二叉树的中序和后序的非递归遍历的逻辑，本质不完全是在模拟系统栈。所以，在我看来，不是一个标准的递归转非递归的思路。如果一定要理解其中的逻辑，只能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;
}其实，对于后序遍历的非递归，还有很多别的写法。但基本上，核心都是：每个节点，必须确保先遍历完了他的左右孩子，才能打印输出这个节点。
还是要再强调一次，这些非递归的思路，在我看来不是普遍的递归转非递归的思路。所以你要理解其中的逻辑，需要去专门看其中的逻辑。不要试图从这个代码中抽象出通用的递归转非递归的思路。通用的递归转非递归的方法，是使用你自己的栈，模拟系统栈调用。我在《玩转算法面试》课程中有讲。
这个代码对应的思路，在我看来是通用的：）
继续加油！：）
相似问题
登录后可查看更多问答，登录/注册
