[LintCode] Binary Search Tree Iterator

silencezwm 发布于2019-08-14 15:33 / 2497人阅读

摘要：建立一个堆栈，先将最左边的结点从大到小压入栈，这样的话，为了实现迭代即返回下一个的函数就要考虑右边的结点。如此，实现函数。

Problem

Design an iterator over a binary search tree with the following rules:

Elements are visited in ascending order (i.e. an in-order traversal)
next() and hasNext() queries run in O(1) time in average.

Example

For the following binary search tree, in-order traversal by using iterator is [1, 6, 10, 11, 12]

Challenge

Extra memory usage O(h), h is the height of the tree.

Super Star: Extra memory usage O(1)

Note

建立一个堆栈，先将最左边的结点从大到小压入栈，这样的话，为了实现迭代即返回下一个node的next()函数就要考虑右边的结点。比如example中的BST，stack第一次pop出来的结点是1，然后就应该把它的右子树结点6压入stack；又如pop出了root结点10以后，就要把11压入堆栈，这样，在pop出11之后，再将12压入堆栈。如此，实现next()函数。

Solution

public class BSTIterator {
    //@param root: The root of binary tree.
    Stack stack;
    public BSTIterator(TreeNode root) {
        stack = new Stack();
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
    }

    //@return: True if there has next node, or false
    public boolean hasNext() {
        return !stack.isEmpty();
    }
    
    //@return: return next node
    public TreeNode next() {
        TreeNode cur = stack.pop();
        TreeNode temp = cur;
        if (cur.right != null) {
            cur = cur.right;
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
        }
        return temp;
    }
}

海外云主机云服务器 binary-search-tree binary-tree binary-search Iterator

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65849.html

[LintCode] Remove Node in Binary Search Tree [理解BS

Problem Given a root of Binary Search Tree with unique value for each node. Remove the node with given value. If there is no such a node with given value in the binary search tree, do nothing. You sho...

陈江龙 2019-08-14 15:33 评论0 收藏0
[LintCode] Insert Node in a Binary Search Tree

摘要：建立两个树结点，先用找到在的位置，让作为的根节点找到的位置后，指向。此时，用代替与连接就可以了。 Problem Given a binary search tree and a new tree node, insert the node into the tree. You should keep the tree still be a valid binary search tr...

Taste 2019-08-14 15:33 评论0 收藏0
[LintCode] Search Range in Binary Search Tree

摘要：重点是根据的性质，先左后根最后右。另一重点是，函数和函数都要用的的参数，记得在函数外层定义。 Problem Given two values k1 and k2 (where k1 < k2) and a root pointer to a Binary Search Tree. Find all the keys of tree in range k1 to k2. i.e. pr...

draveness 2019-08-14 15:12 评论0 收藏0
[Leetcode - Tree] Binary Search Tree Iterator

摘要：解题思路对于二叉搜索树，我们很容易会想到使用栈和队列来解决问题，本题是要求实现一个对二叉搜索树的遍历器，要求每次可以返回最小的节点值，我们使用栈。 Binary Search Tree IteratorImplement an iterator over a binary search tree (BST). Your iterator will be initialized with...

jsyzchen 2019-08-16 10:26 评论0 收藏0
[Leetcode] Binary Search Tree Iterator 二叉搜素树迭代器

摘要：代码先找到第一个节点，并把路径入栈栈为空时不再有下一个栈顶是待返回元素如果该元素有右节点，把它的右节点及右节点的所有左边节点都压入栈中 Binary Search Tree Iterator 最新更新：https://yanjia.me/zh/2019/02/... Implement an iterator over a binary search tree (BST). Your...

shixinzhang 2019-08-14 12:36 评论0 收藏0