173. 二叉搜索树迭代器

https://leetcode-cn.com/problems/binary-search-tree-iterator/

解法一：

递归中序遍历存到数组中，依次访问即可。

解法二：

按 94.二叉树的中序遍历 解法二的非递归方法，进行相应改造

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class BSTIterator:

    def __init__(self, root: TreeNode):
        p = root
        self.stack = []  #全局栈
        #初始先走到最左子，路径依次入栈
        while p:
            self.stack.append(p)
            p = p.left

    def next(self) -> int:
        p = self.stack.pop()  #出栈。不用考虑栈空，题目假设不为空
        res = p  #访问的结点
        #如有右子，按如上方法处理
        if p.right:
            p = p.right
            while p:
                self.stack.append(p)
                p = p.left
        return res.val
        
    def hasNext(self) -> bool:
        #查看栈是否为空即可
        return True if len(self.stack) > 0 else False