成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[LintCode] Binary Search Tree Iterator

silencezwm / 2689人閱讀

摘要：建立一個堆棧，先將最左邊的結(jié)點(diǎn)從大到小壓入棧，這樣的話，為了實(shí)現(xiàn)迭代即返回下一個的函數(shù)就要考慮右邊的結(jié)點(diǎn)。如此，實(shí)現(xiàn)函數(shù)。

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]

   10
 /    
1      11
        
  6       12
Challenge

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

Super Star: Extra memory usage O(1)

Note

建立一個堆棧，先將最左邊的結(jié)點(diǎn)從大到小壓入棧，這樣的話，為了實(shí)現(xiàn)迭代即返回下一個node的next()函數(shù)就要考慮右邊的結(jié)點(diǎn)。比如example中的BST，stack第一次pop出來的結(jié)點(diǎn)是1，然后就應(yīng)該把它的右子樹結(jié)點(diǎn)6壓入stack；又如pop出了root結(jié)點(diǎn)10以后，就要把11壓入堆棧，這樣，在pop出11之后，再將12壓入堆棧。如此，實(shí)現(xiàn)next()函數(shù)。

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

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/65849.html

相關(guān)文章

  • [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...

    陳江龍 評論0 收藏0

  • [LintCode] Insert Node in a Binary Search Tree

    摘要：建立兩個樹結(jié)點(diǎn)，先用找到在的位置，讓作為的根節(jié)點(diǎn)找到的位置后，指向。此時，用代替與連接就可以了。 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 評論0 收藏0

  • [LintCode] Search Range in Binary Search Tree

    摘要：重點(diǎn)是根據(jù)的性質(zhì)，先左后根最后右。另一重點(diǎn)是，函數(shù)和函數(shù)都要用的的參數(shù)，記得在函數(shù)外層定義。 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 評論0 收藏0

  • [Leetcode] Binary Search Tree Iterator 二叉搜素樹迭代器

    摘要：代碼先找到第一個節(jié)點(diǎn)，并把路徑入棧棧為空時不再有下一個棧頂是待返回元素如果該元素有右節(jié)點(diǎn)，把它的右節(jié)點(diǎn)及右節(jié)點(diǎn)的所有左邊節(jié)點(diǎn)都壓入棧中 Binary Search Tree Iterator 最新更新：https://yanjia.me/zh/2019/02/... Implement an iterator over a binary search tree (BST). Your...

    shixinzhang 評論0 收藏0

  • [Leetcode - Tree] Binary Search Tree Iterator

    摘要：解題思路對于二叉搜索樹，我們很容易會想到使用棧和隊(duì)列來解決問題，本題是要求實(shí)現(xiàn)一個對二叉搜索樹的遍歷器，要求每次可以返回最小的節(jié)點(diǎn)值，我們使用棧。 Binary Search Tree IteratorImplement an iterator over a binary search tree (BST). Your iterator will be initialized with...

    jsyzchen 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<