溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊(cè)×
其他方式登錄
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶服務(wù)條款》

二叉搜索樹迭代器指的是什么

發(fā)布時(shí)間：2022-01-15 11:29:04 來源：億速云 閱讀：87 作者：柒染 欄目：大數(shù)據(jù)

這篇文章給大家介紹二叉搜索樹迭代器指的是什么，內(nèi)容非常詳細(xì)，感興趣的小伙伴們可以參考借鑒，希望對(duì)大家能有所幫助。

實(shí)現(xiàn)一個(gè)二叉搜索樹迭代器。你將使用二叉搜索樹的根節(jié)點(diǎn)初始化迭代器。

調(diào)用 next() 將返回二叉搜索樹中的下一個(gè)最小的數(shù)。

示例：

二叉搜索樹迭代器指的是什么

BSTIterator iterator = new BSTIterator(root); iterator.next();    

// 返回 3 iterator.next();    

// 返回 7 iterator.hasNext(); 

// 返回 true iterator.next();    

// 返回 9 iterator.hasNext(); 

// 返回 true iterator.next();    

// 返回 15 iterator.hasNext(); 

// 返回 true iterator.next();    

// 返回 20 iterator.hasNext(); 

// 返回 false

答案：

 1class BSTIterator {
 2
 3    private Stack<TreeNode> stack = new Stack<TreeNode>();
 4
 5    public BSTIterator(TreeNode root) {
 6        pushAll(root);
 7    }
 8
 9    public boolean hasNext() {
10        return !stack.isEmpty();
11    }
12
13    public int next() {
14        TreeNode tmpNode = stack.pop();
15        pushAll(tmpNode.right);
16        return tmpNode.val;
17    }
18
19    private void pushAll(TreeNode node) {
20        for (; node != null; stack.push(node), node = node.left) ;
21    }
22}

解析：
如果對(duì)二叉樹的dfs（深度優(yōu)先搜索）比較熟悉的話，這題很容易理解。

關(guān)于二叉搜索樹迭代器指的是什么就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，可以學(xué)到更多知識(shí)。如果覺得文章不錯(cuò)，可以把它分享出去讓更多的人看到。

向AI問一下細(xì)節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手