欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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

 更新時(shí)間：2021年08月02日 17:17:21   作者：Grandyang  
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(173.二叉搜索樹迭代器),本篇文章通過簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(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.

這道題主要就是考二叉樹的中序遍歷的非遞歸形式，需要額外定義一個(gè)棧來(lái)輔助，二叉搜索樹的建樹規(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/C++利用原生套接字抓取FTP數(shù)據(jù)包

    C/C++利用原生套接字抓取FTP數(shù)據(jù)包

    這篇文章主要為大家詳細(xì)介紹了如何基于原始套接字的網(wǎng)絡(luò)數(shù)據(jù)包捕獲與分析工具,通過實(shí)時(shí)監(jiān)控網(wǎng)絡(luò)流量,實(shí)現(xiàn)抓取流量包內(nèi)的FTP通信數(shù)據(jù),需要的小伙伴可以參考下
    2023-12-12

    • 最新評(píng)論