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

来源：6-3 运用栈模拟递归

隐士Muya

2018-06-06

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

写回答

1回答

liuyubobobo

2018-06-07

当然可以啦。如果比较深刻的理解了这一小节我讲的模拟栈的做法，可以看看这个代码，理解一下其中的逻辑：）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

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

参考代码：

最后，对于二叉树的非递归遍历，有一个更神奇的方法，使用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

加油！：）

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题，高频算法题解析，强化训练

7408 学习 · 1150 问题

相似问题

回答 1

回答 1

回答 1

回答 1

回答 1