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(); */