LeetCode: 173. Binary Search Tree Iterator

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.

解题思路

构建中序遍历的线索二叉树(利用哈希表(unordered_map)来存储线索), 线索的顺序就是迭代器遍历的顺序。

AC 代码

/** * 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) {
        TreeNode* pre = nullptr;
        makeTreeNextMap(root, pre);
        tree2Next[pre] = nullptr;
        curNode = tree2Next[nullptr];
    }

    /** @return whether we have a next smallest number */
    bool hasNext() {
        return !(curNode == nullptr);
    }

    /** @return the next smallest number */
    int next() {
        int cur = curNode->val;
        curNode = tree2Next[curNode];

        return cur;
    }
private:
    void makeTreeNextMap(TreeNode* root, TreeNode*& pre)
    {
        if(root == nullptr) return ;

        makeTreeNextMap(root->left, pre);
        tree2Next[pre] = root;
        pre=root;
        makeTreeNextMap(root->right, pre);
    }

private:
    unordered_map<TreeNode*, TreeNode*> tree2Next; 
    TreeNode* curNode;
};

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

相关推荐

不愿透露姓名的神秘牛友
02-16 22:33
杉川机器人 嵌入式工程师 18.0k*13.0, 年终奖1~9个月浮动
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
02-12 10:05
小米集团 算法工程师 28.0k*15.0
泡沫灬一触即破:楼上那个看来是看人拿高薪,自己又不如意搁这泄愤呢是吧,看你过往评论很难不怀疑你的精神状态
点赞 评论 收藏
分享
02-05 08:18
四川大学 Java
在思考的熊熊很讨厌吃香菜:不是,我门头沟学院呢?这都没排上?
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务