# 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