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

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

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

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

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.

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

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