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

資訊專欄INFORMATION COLUMN

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

shixinzhang / 2792人閱讀

摘要：代碼先找到第一個(gè)節(jié)點(diǎn)，并把路徑入棧棧為空時(shí)不再有下一個(gè)棧頂是待返回元素如果該元素有右節(jié)點(diǎn)，把它的右節(jié)點(diǎn)及右節(jié)點(diǎn)的所有左邊節(jié)點(diǎn)都?jí)喝霔Ｖ?/p>

Binary Search Tree Iterator 最新更新：https://yanjia.me/zh/2019/02/... 
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.
棧法 復(fù)雜度

時(shí)間 O(N) 空間 O(1)

思路

這道題和Inorder Successor in BST很像，區(qū)別在于Successor那題是給定節(jié)點(diǎn)求下一個(gè)，而這題是要做一個(gè)迭代器，返回當(dāng)前指向的值，其實(shí)就是求上次返回的節(jié)點(diǎn)的下一個(gè)，本質(zhì)是一樣的。題目要求最多只能用O(H)的空間，所以思路也和那題一樣，用一個(gè)Stack記錄從根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的路徑。next的時(shí)候就返回Stack最上面的元素。不過(guò)拿出最上面的元素后，我們還要看一下這個(gè)被返回的元素是否有右節(jié)點(diǎn)，如果有的話，就把它的右節(jié)點(diǎn)及右節(jié)點(diǎn)的所有左邊節(jié)點(diǎn)都?jí)喝霔Ｖ?。另外，初始化棧時(shí)，我們要找到最左邊的節(jié)點(diǎn)，也就是中序遍歷的第一個(gè)節(jié)點(diǎn)，并把根到第一個(gè)節(jié)點(diǎn)的路徑都?jí)喝霔！?/p>

這題還可以結(jié)合Binary Tree Inorder Traverse的迭代做法一起理解。他們的共同點(diǎn)都是用一個(gè)棧，將最左邊的節(jié)點(diǎn)都?jí)喝霔！?/p> 代碼 

public class BSTIterator {
    
    Stack stk;

    public BSTIterator(TreeNode root) {
        stk = new Stack();
        // 先找到第一個(gè)節(jié)點(diǎn)，并把路徑入棧
        while(root != null){
            stk.push(root);
            root = root.left;
        }
    }

    public boolean hasNext() {
        // 棧為空時(shí)不再有下一個(gè)
        return !stk.isEmpty();
    }

    public int next() {
        // 棧頂是待返回元素
        TreeNode curr = stk.pop();
        int res = curr.val;
        // 如果該元素有右節(jié)點(diǎn)，把它的右節(jié)點(diǎn)及右節(jié)點(diǎn)的所有左邊節(jié)點(diǎn)都?jí)喝霔Ｖ?        if(curr.right != null){
            curr = curr.right;
            while(curr != null){
                stk.push(curr);
                curr = curr.left;
            }
        }
        return res;
    }
}

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

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

相關(guān)文章

  • [Leetcode - Tree] Binary Search Tree Iterator

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

    jsyzchen 評(píng)論0 收藏0

  • [Leetcode] Closest Binary Search Tree Value 最近二叉搜索

    摘要：遞歸法復(fù)雜度時(shí)間空間思路根據(jù)二叉樹的性質(zhì)，我們知道當(dāng)遍歷到某個(gè)根節(jié)點(diǎn)時(shí)，最近的那個(gè)節(jié)點(diǎn)要么是在子樹里面，要么就是根節(jié)點(diǎn)本身。因?yàn)槲覀冎离x目標(biāo)數(shù)最接近的數(shù)肯定在二叉搜索的路徑上。 Closest Binary Search Tree Value I Given a non-empty binary search tree and a target value, find the va...

    AlphaWallet 評(píng)論0 收藏0

  • 前端 | 每天一個(gè) LeetCode

    摘要：在線網(wǎng)站地址我的微信公眾號(hào)完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語(yǔ)言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號(hào)： showImg(htt...

    張漢慶 評(píng)論0 收藏0

  • leetcode講解--94. Binary Tree Inorder Traversal

    摘要：題目地址嗯，經(jīng)典的題目，中序遍歷二叉樹。代碼如下中序遍歷先序遍歷后序遍歷是不是簡(jiǎn)單的不要不要的，遞歸就是這么美。右孩子后壓棧全部釋放出來(lái)嗯，總的來(lái)說(shuō)用迭代遍歷確實(shí)燒腦，沒(méi)什么性能上的特殊需求還是用遞歸寫法吧，對(duì)程序員友好哦。 94. Binary Tree Inorder Traversal Given a binary tree, return the inorder travers...

    henry14 評(píng)論0 收藏0

  • [Leetcode] Validate Binary Search Tree 驗(yàn)證二叉搜索樹

    摘要：注意這里的結(jié)構(gòu)和不同的二叉樹遍歷一樣，如果到空節(jié)點(diǎn)就返回，否則遞歸遍歷左節(jié)點(diǎn)和右節(jié)點(diǎn)。唯一不同是加入了和，所以要在遞歸之前先判斷是否符合和的條件。代碼如果該節(jié)點(diǎn)大于上限返回假如果該節(jié)點(diǎn)小于下限返回假遞歸判斷左子樹和右子樹 Validate Binary Search Tree Given a binary tree, determine if it is a valid binary...

    fuchenxuan 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<