C++实现LeetCode(173.二叉搜索树迭代器)

LeetCode(173.二叉搜索树迭代器)是一道比较好的二叉搜索树遍历题目，它的要求是实现一个二叉搜索树迭代器，支持in-order遍历二叉搜索树，并且实现next()和has_next()两个函数。

解法

本题的难点在于要求使用迭代器实现中序遍历，而不是递归。我们可以通过栈来实现中序遍历，即先把根节点压入栈中，然后每次弹出栈顶元素，并将其右子节点（如果有）与左子节点（如果有）依次压入栈中。这样我们就能保证每次弹出的元素都是当前最小的元素了。

有了上述的中序遍历实现，我们只需要在next()和has_next()函数中按照上述方法实现就可以了。

具体代码如下：

class BSTIterator:

    def __init__(self, root: TreeNode):

        self.stack = []

        while root:

            self.stack.append(root)

            root = root.left

    def next(self) -> int:

        if not self.has_next():

            return None

        node = self.stack.pop()

        res = node.val

        node = node.right

        while node:

            self.stack.append(node)

            node = node.left

        return res

    def has_next(self) -> bool:

        return bool(self.stack)