C++實(shí)現(xiàn)LeetCode(173.二叉搜索樹(shù)迭代器)

更新時(shí)間：2021年08月02日 17:17:21 作者：Grandyang

這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(173.二叉搜索樹(shù)迭代器),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下

[LeetCode] 173.Binary Search Tree Iterator 二叉搜索樹(shù)迭代器

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.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

這道題主要就是考二叉樹(shù)的中序遍歷的非遞歸形式，需要額外定義一個(gè)棧來(lái)輔助，二叉搜索樹(shù)的建樹(shù)規(guī)則就是左<根<右，用中序遍歷即可從小到大取出所有節(jié)點(diǎn)。代碼如下：

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class BSTIterator {
public:
    BSTIterator(TreeNode *root) {
        while (root) {
            s.push(root);
            root = root->left;
        }
    }

    /** @return whether we have a next smallest number */
    bool hasNext() {
        return !s.empty();
    }

    /** @return the next smallest number */
    int next() {
        TreeNode *n = s.top();
        s.pop();
        int res = n->val;
        if (n->right) {
            n = n->right;
            while (n) {
                s.push(n);
                n = n->left;
            }
        }
        return res;
    }
private:
    stack<TreeNode*> s;
};

/**
 * Your BSTIterator will be called like this:
 * BSTIterator i = BSTIterator(root);
 * while (i.hasNext()) cout << i.next();
 */

您可能感興趣的文章:

相關(guān)文章

C語(yǔ)言廣播的使用詳解
顧名思義可以把自己的數(shù)據(jù)發(fā)送給在特定范圍內(nèi)的所有人；我們網(wǎng)絡(luò)編程中的廣播一般是通過(guò)特定的廣播地址把自己的數(shù)據(jù)發(fā)送給局域網(wǎng)內(nèi)當(dāng)前在線的客戶(hù)端
2022-05-05
C語(yǔ)言?xún)?nèi)存泄漏常見(jiàn)情況及解決方案詳解
這篇文章主要為大家介紹了C語(yǔ)言?xún)?nèi)存泄漏常見(jiàn)情況及解決方案詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
2023-08-08
C語(yǔ)言中輸入輸出流與緩沖區(qū)的深入講解
一般情況下，由鍵盤(pán)輸入的字符并沒(méi)有直接送入程序，而是被存儲(chǔ)在一個(gè)緩沖區(qū)當(dāng)中。下面這篇文章主要給大家介紹了關(guān)于C語(yǔ)言中輸入輸出流與緩沖區(qū)的相關(guān)資料，文中通過(guò)示例代碼介紹的非常詳細(xì)，需要的朋友可以參考下
2018-09-09
C++實(shí)現(xiàn)strcmp字符串比較的深入探討
本篇文章是對(duì)使用C++實(shí)現(xiàn)strcmp字符串比較進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下
2013-05-05
C語(yǔ)言中宏和函數(shù)的9個(gè)區(qū)別詳解
C語(yǔ)言中的宏和函數(shù)是非常相似的，它們都可以完成類(lèi)似的功能。本文為大家整理了C語(yǔ)言中宏和函數(shù)的9個(gè)區(qū)別，感興趣的小伙伴可以跟隨小編一起了解一下
2023-04-04
C++小知識(shí):大于0并不意味著等于1
今天小編就為大家分享一篇關(guān)于C++小知識(shí):大于0并不意味著等于1，小編覺(jué)得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來(lái)看看吧
2019-01-01
學(xué)習(xí)C語(yǔ)言要掌握的幾個(gè)庫(kù)
本文給大家分享的是網(wǎng)友提出的學(xué)習(xí)C語(yǔ)言要掌握的幾個(gè)庫(kù)，這里分享給大家，有需要的小伙伴可以參考下。
2015-07-07
C++實(shí)現(xiàn)電子時(shí)鐘效果
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)電子時(shí)鐘效果，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2022-05-05
C語(yǔ)言設(shè)計(jì)簡(jiǎn)易電話簿
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言設(shè)計(jì)簡(jiǎn)易電話簿，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2019-12-12
C語(yǔ)言代碼實(shí)現(xiàn)點(diǎn)餐系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)點(diǎn)餐系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2020-07-07