Skip to content

173 binary search tree iterator

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


回到顶部