关于二分搜索树的非递归遍历问题

Question

想问一下bobo老师关于后序非递归

我自己在网上查找了 前中后 三种非递归方式，其中 前序与后序 看的懂。

后序这个 我完全get不到这样写的点。。。

请老师解惑

Answer 1

liuyubobobo 2018-07-04 12:36:19

如果你已经学习了二叉树的前序遍历的非递归代码，仔细观察，其实这个代码就是一个“反向”的前序遍历代码。所谓的“反向”，是指对于每个节点，先找右子树，再找左子树：）

这样进行“反向”的前序遍历，最终得到的遍历结果（存储在了output中），再反转过来，就是后序遍历的结果：）这个翻转过程表现在最后的while循环中，output的元素是从后向前输出的（使用pop）：）

• 提问者 丶远走高飞 #1

  非常感谢！

• 提问者 丶远走高飞 #2

  啊 我没想到老师的回答是这样的。。可是这样 没说服力啊。就为什么要这样做。我还是不是很懂。。

• 提问者 丶远走高飞 #3

  我按照老师讲课的思路理解， 首先后序遍历相当于第三遍到达节点时，访问该结点，正常顺序来说是，先访问左子树，再访问右子树，然后回到该结点时再访问该结点，按照前序非递归的写法，在第二次访问该结点，也就是访问右子树时，就已经将该元素pop出来，所以在访问完右子树后，无法再回到该结点。因此问题出在我们需要在访问完右子树后，再回到该结点，而后序非递归遍历就是这样做的，它先访问右子树，访问完了以后，就可以pop回到该结点。我疑惑在于刚好将output 一个个pop出来 就是后序遍历。。。为什么

点开查看后面1条评论