Leetcode 173. Binary Search Tree Iterator 可以使用模拟栈的解法来做吗？

Question

Leetcode 173 可以使用这种解法来写吗？ 请问应该怎么做比较好呢？

Answer 1

liuyubobobo 2018-06-07 03:32:14

当然可以啦。如果比较深刻的理解了这一小节我讲的模拟栈的做法，可以看看这个代码，理解一下其中的逻辑：）https://github.com/liuyubobobo/Play-Leetcode/blob/master/0173-Binary-Search-Tree-Iterator/cpp-0173/main2.cpp

对于这个问题，当然，也可以改进二叉树经典非递归遍历的逻辑。如果你了解二叉树经典非递归遍历的写法，可以参考这个代码：）https://github.com/liuyubobobo/Play-Leetcode/blob/master/0173-Binary-Search-Tree-Iterator/cpp-0173/main3.cpp

对于二叉树的经典非递归遍历，在这个课程的补充代码中有给出。有兴趣的同学可以研究自学（或者复习，一般大学课堂上都会介绍的。）。不过个人认为，所谓的经典非递归代码，其实对于深刻理解递归帮助不大，更是一种在二叉树领域的特殊算法。所以在这个课程中并没有进行特殊强调。不过从学习的角度，还是有必要掌握的：）

参考代码：

二叉树前序遍历的非递归：https://github.com/liuyubobobo/Play-with-Algorithm-Interview/tree/master/06-Stack-and-Queue/Course%20Code%20(C++)/Optional-01-Classic-Non-Recursive-Preorder-Traversal

二叉树中序遍历的非递归：https://github.com/liuyubobobo/Play-with-Algorithm-Interview/tree/master/06-Stack-and-Queue/Course%20Code%20(C++)/Optional-02-Classic-Non-Recursive-Inorder-Traversal

二叉树后序遍历的非递归：https://github.com/liuyubobobo/Play-with-Algorithm-Interview/tree/master/06-Stack-and-Queue/Course%20Code%20(C++)/Optional-03-Classic-Non-Recursive-Postorder-Traversal

最后，对于二叉树的非递归遍历，有一个更神奇的方法，使用O(n)的时间复杂度和O(1)的空间复杂度（即不适用栈！），称为Morris遍历法。Morris遍历近乎不可能出现在面试中。不过有兴趣，也可以自己研究看。课程的补充代码中也给出了实现，可以参考这里：https://github.com/liuyubobobo/Play-with-Algorithm-Interview/tree/master/06-Stack-and-Queue/Course%20Code%20(C++)/Optional-04-Binary-Tree-Morris-Traversal

加油！：）