Leetcode: Binary Search Tree Iterator

卡尔曼和玻尔兹曼谁曼

发布于 2019-01-22 17:21:44

3360

发布于 2019-01-22 17:21:44

题目： Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree. 要求调用next方法依次返回二叉搜索树下一个最小的值。

二叉搜索树又叫二叉查找树或二叉排序树（Binary Search Tree），它或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。

思路：根据二叉树搜索树的性质，维护一个栈，首先从根节点开始，每次迭代地将根节点的左孩子压入栈，直到左孩子为空为止。

调用next()方法时，弹出栈顶，如果被弹出的元素拥有右孩子，则以右孩子为根，将其左孩子迭代压栈。

C++参考代码：

/**
 * Definition for binary tree
 * struct TreeNode
 * {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class BSTIterator
{
private:
    stack<TreeNode*> nodeStack;
    void pushLeft(TreeNode *node)
    {
        while (node)
        {
            nodeStack.push(node);
            node = node->left;
        }
    }
public:
    BSTIterator(TreeNode *root)
    {
        pushLeft(root);
    }

    /** @return whether we have a next smallest number */
    bool hasNext()
    {
        return !nodeStack.empty();
    }

    /** @return the next smallest number */
    int next()
    {
        TreeNode *small = nodeStack.top();
        nodeStack.pop();
        pushLeft(small->right);
        return small->val;
    }
};

/**
 * Your BSTIterator will be called like this:
 * BSTIterator i = BSTIterator(root);
 * while (i.hasNext()) cout << i.next();
 */

C#参考代码：

/**
 * Definition for binary tree
 * public class TreeNode
 * {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */

public class BSTIterator
{
    private Stack<TreeNode> nodeStack;

    private void PushLeft(TreeNode node)
    {
        while (node != null)
        {
            nodeStack.Push(node);
            node = node.left;
        }
    }

    public BSTIterator(TreeNode root)
    {
        nodeStack = new Stack<TreeNode>();
        PushLeft(root);
    }

    /** @return whether we have a next smallest number */
    public bool HasNext()
    {
        return nodeStack.Count > 0 ? true : false;
    }

    /** @return the next smallest number */
    public int Next()
    {
        TreeNode small = nodeStack.Pop();
        PushLeft(small.right);
        return small.val;
    }
}

/**
 * Your BSTIterator will be called like this:
 * BSTIterator i = new BSTIterator(root);
 * while (i.HasNext()) v[f()] = i.Next();
 */

Python参考代码： Python中stack可以使用list进行模拟

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

class BSTIterator:
    # @param root, a binary search tree's root node
    def __init__(self, root):
        self.__nodeStack = list()
        self.__pushLeft(root)

    def __pushLeft(self, node):
        while node is not None:
            self.__nodeStack.append(node)
            node = node.left

    # @return a boolean, whether we have a next smallest number
    def hasNext(self):
        return self.__nodeStack

    # @return an integer, the next smallest number
    def next(self):
        small = self.__nodeStack.pop()
        self.__pushLeft(small.right)
        return small.val


# Your BSTIterator will be called like this:
# i, v = BSTIterator(root), []
# while i.hasNext(): v.append(i.next())

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2015年03月29日，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树