[LintCode] Binary Search Tree Iterator

silencezwm 發布于2019-08-14 15:33 / 2642人閱讀

摘要：建立一個堆棧，先將最左邊的結點從大到小壓入棧，這樣的話，為了實現迭代即返回下一個的函數就要考慮右邊的結點。如此，實現函數。

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;
    }
}

GPU云服務器云服務器 binary-search-tree binary-tree binary-search Iterator

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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] 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
[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