[Leetcode]173. Binary Search Tree Iterator(C++)

题目描述

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.

You may assume that next() call will always be valid, that is, there will be at least a next smallest number in the BST when next() is called.

解题思路

这道题比较简单的做法是在构造函数通过前序遍历将二叉树遍历一遍并将结果放入一个队列中，这样查询和返回下一元素都只需要常数时间，代码如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
#include <queue>

class BSTIterator {
public:
    BSTIterator(TreeNode* root) { dfs(root); }

    /** @return the next smallest number */
    int next() {
        int val = node_list.front();
        node_list.pop();
        return val;
    }

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

private:
    std::queue<int> node_list;

private:
    void dfs(TreeNode* node) {
        if (node == nullptr) return;
        dfs(node->left);
        node_list.push(node->val);
        dfs(node->right);
    }
};

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator* obj = new BSTIterator(root);
 * int param_1 = obj->next();
 * bool param_2 = obj->hasNext();
 */

时间复杂度: O(n) for constructor, O(1) for the other twos operations
空间复杂度: O(n) for constructor, O(1) for the other twos operations

GitHub 代码同步地址： 173.BinarySearchTreeIterator.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions