关于中序遍历和后序遍历的非递归写法

Question

波波老师，BST的非递归中序遍历和后序遍历，您有上传代码吗？

我在书上、还有网上找的资料，遍历的非递归写法，前序写法都没有你那个酷，感觉你的那个很巧妙。

中序和后序想模仿，但是写不出来，很难受！

Answer 1

liuyubobobo 2018-08-04 22:09:38

可以参考这里：https://github.com/liuyubobobo/Play-with-Data-Structures/tree/master/06-Binary-Search-Tree/Optional-03-Binary-Tree-Classic-Nonrecursive-Traversal 

更进一步，如果对Morris遍历感兴趣，可以参考这里：https://github.com/liuyubobobo/Play-with-Data-Structures/tree/master/06-Binary-Search-Tree/Optional-05-Binary-Tree-Morris-Traversal/src   

Morris遍历可以做到使用O(1)的空间复杂度遍历二叉树。不过我从没听说过面试有问它的。这种问题在竞赛里也没用武之地。爱好者闲的没事儿可以研究一下：）

加油！：）

• 提问者 行息衍 #1

  一直对照代码仓写。。竟然没发现。有劳老师了

• 提问者 行息衍 #2

  很酷！

• liuyubobobo 回复 提问者 行息衍 #3

  更进一步，如果对Morris遍历感兴趣，可以参考这里：https://github.com/liuyubobobo/Play-with-Data-Structures/tree/master/06-Binary-Search-Tree/Optional-05-Binary-Tree-Morris-Traversal/src Morris遍历可以做到使用O(1)的空间复杂度遍历二叉树。不过我从没听说过面试有问它的。这种问题在竞赛里也没用武之地。爱好者闲的没事儿可以研究一下：）

点开查看后面1条评论