各位题友大家好！ 今天是 @负雪明烛 坚持日更的第 63 天。今天力扣上的每日一题是「173. 二叉搜索树迭代器」。

解题思路

题目给出的树是：二叉搜索树（BST）。二叉搜索树最重要的性质是：二叉搜索树的中序遍历是有序的。今天这个题目直接让我们「中序遍历」，我建议题目可以改为：实现二叉搜索树的升序迭代器。

具体到题目实现上，我们可以有两个方法：
- 提前保存全部节点
- 迭代时计算 next 节点

方法一：提前保存全部节点

这个方法比较简单，提前把 BST 的中序遍历结果保存到一个队列里面，当调用 next() 方法的时候，就从队列头部弹出一个元素。

树的中序中序遍历应该是基础知识，我就不讲了。

代码如下：

  1. # Definition for a binary tree node.
  2. # class TreeNode(object):
  3. #     def __init__(self, val=0, left=None, right=None):
  4. #         self.val = val
  5. #         self.left = left
  6. #         self.right = right
  7. class BSTIterator(object):
  9.     def __init__(self, root):
  10.         self.queue = collections.deque()
  11.         self.inOrder(root)
  13.     def inOrder(self, root):
  14.         if not root: return
  15.         self.inOrder(root.left)
  16.         self.queue.append(root.val)
  17.         self.inOrder(root.right)
  19.     def next(self):
  20.         return self.queue.popleft()
  23.     def hasNext(self):
  24.         return len(self.queue) > 0
  • 时间复杂度：构造函数是 $O(N)$；调用 next() 方法的时间复杂度是 $O(1)$。
  • 空间复杂度：$O(N)$，使用了队列保存了所有元素。

方法二：迭代时计算 next 节点

在前几天的设计迭代器的每日一题中，我说过提前把所有的值遍历并且保存起来的做法并不好，不是面试官想要的。比如我举个场景：想通过 BST 的迭代器，判断 BST 中有没有 数值x。此时哪怕 数值x 是 BST 迭代器的第一个元素，上面的方法也会先把所有的值都遍历出来，时间复杂度到了$O(N)$。

所以，设计迭代器的时候，应避免提前把所有的值都遍历出来；最好能设计成遍历过程中求 next 节点。那就需要用迭代方法了。

把递归转成迭代，基本想法就是用栈。

迭代思路是：栈中只保留左节点。

思路来自递归：中序遍历的访问顺序是 左子树 -> 根节点 -> 右子树 的顺序，对于 左子树 和 右子树 也进行递归。因此实际遍历顺序是从根节点开始一路到底找到最左边的叶子节点，然后向上弹出访问 该叶子节点 的根节点，然后访问了 该叶子节点的根节点的右子树 进行同样的操作。

中序遍历流程如下图所示：

根据上面的遍历顺序，我们得出迭代的思路：

  • 构造方法：一路到底，把根节点和它的所有左节点放到栈中；
  • 调用 next() 方法：弹出栈顶的节点；
    • 如果它有右子树，则对右子树一路到底，把它和它的所有左节点放到栈中。
    • 如果它没有右子树，不用操作；

代码如下：

  1. # Definition for a binary tree node.
  2. # class TreeNode(object):
  3. #     def __init__(self, val=0, left=None, right=None):
  4. #         self.val = val
  5. #         self.left = left
  6. #         self.right = right
  7. class BSTIterator(object):
  9.     def __init__(self, root):
  10.         self.stack = []
  11.         while root:
  12.             self.stack.append(root)
  13.             root = root.left
  15.     def next(self):
  16.         cur = self.stack.pop()
  17.         node = cur.right
  18.         while node:
  19.             self.stack.append(node)
  20.             node = node.left
  21.         return cur.val
  23.     def hasNext(self):
  24.         return len(self.stack) > 0
  • 时间复杂度：$O(1)$，调用 next() 方法的时候，如果栈顶元素有右子树，则把所有右边节点即其所有左孩子全部放到了栈中，下次调用 next() 的时候，直接访问栈顶就可以了，均摊之后时间复杂度是 $O(1)$。
  • 空间复杂度：$O(h)$，h 为数的高度，因为栈中只保留了左节点，栈中元素最多的时候，就是树的高度。

刷题心得

今天题目的迭代写法来自对递归的理解。把递归弄懂了，才可能写出这种迭代写法。

参考资料：【LeetCode】代码模板，刷题必会

OK，以上就是 @负雪明烛 写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。

关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。

祝大家牛年大吉！AC 多多，Offer 多多！我们明天再见！