173._binary_search_tree_iterator.md

173. Binary Search Tree Iterator

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

难度: Medium

同样没有听题目要求，一开始就取巧，用InOrder，这样得到BSF有序排列，然后使用

class BSTIterator(object):
    def __init__(self, root):
        """
        :type root: TreeNode
        """
        self.root = root
        self.lst = []
        self.inOrder(root)
        self.lst.reverse()
            
        

    def hasNext(self):
        """
        :rtype: bool
        """
        return self.lst != []
        

    def next(self):
        """
        :rtype: int
        """
        return self.lst.pop()
    
    def inOrder(self, root):
        if root == None:
            return
        self.inOrder(root.left)
        self.lst.append(root.val)
        self.inOrder(root.right)
        

谷歌了一下，得到如何满足题目要求的hint，从root开始，往左走，把左孩子压入stack，直到左边为空。

然后开始取node，如果node有右孩子，则同样要把node的右孩子的所有左孩子全部append入stack，画了一个图，可行。

class BSTIterator(object):
    def __init__(self, root):
        """
        :type root: TreeNode
        """
        self.root = root
        self.stack = []
        self.pushAllLeft(root)
        

    def hasNext(self):
        """
        :rtype: bool
        """
        return self.stack != []
        

    def next(self):
        """
        :rtype: int
        """
        if self.hasNext():
            cur = self.stack.pop()
            if cur.right:
                self.pushAllLeft(cur.right)
            return cur.val
            
    def pushAllLeft(self, node):
        """
        :type node: TreeNode
        """
        cur = node
        while cur:
            self.stack.append(cur)
            cur = cur.left