[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.

Callingnext()will return the next smallest number in the BST.

Note:next()andhasNext()should run in average O(1) time and uses O(h) memory, wherehis the height of the tree.

【分析】

中序遍历

【代码】

/*********************************
*   日期：2015-01-03
*   作者：SJF0115
*   题目: 173.Binary Search Tree Iterator
*   来源：https://oj.leetcode.com/problems/binary-search-tree-iterator/
*   结果：AC
*   来源：LeetCode
*   博客：
**********************************/
#include <iostream>
#include <stack>
#include <vector>
using namespace std;

// 二叉查找树节点
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 插入
void TreeInsert(TreeNode*& root,int val){
    // 创建新节点
    TreeNode* node = new TreeNode(val);
    // 空树
    if(root == NULL){
        root = node;
        return;
    }//if
    TreeNode *pre = NULL;
    TreeNode *p = root;
    // 寻找插入位置
    while(p){
        // 父节点
        pre = p;
        // 沿左子树方向下降
        if(val < p->val){
            p = p->left;
        }//if
        // 沿右子树方向下降
        else{
            p = p->right;
        }//else
    }//while
    // 左子结点处插入
    if(val < pre->val){
        pre->left = node;
    }//if
    // 右子结点处插入
    else{
        pre->right = node;
    }//else
}
// 创建二叉查找树
TreeNode* TreeCreate(vector<int> num){
    TreeNode *root = NULL;
    int len = num.size();
    if(len == 0){
        return root;
    }//if
    for(int i = 0;i < len;i++){
        TreeInsert(root,num[i]);
    }//for
    return root;
}
class BSTIterator {
public:
    BSTIterator(TreeNode *root) {
        TreeNode *p = root;
        // 沿左子树下降
        while(p){
            s.push(p);
            p = p->left;
        }//while
    }
    /** @return whether we have a next smallest number */
    bool hasNext() {
        if(!s.empty()){
            return true;
        }//if
        return false;
    }

    /** @return the next smallest number */
    int next() {
        TreeNode *p = NULL;
        // 出栈
        p = s.top();
        s.pop();
        int val = p->val;
        // 转向右子树
        if(p->right){
            p = p->right;
            // 沿左子树下降
            while(p){
                s.push(p);
                p = p->left;
            }//while
        }//if
        return val;
    }
private:
    stack<TreeNode*> s;
};

int main() {
    // -1代表NULL
    vector<int> num = {8,3,1,10,6,14,4,7,13};
    TreeNode *root = TreeCreate(num);
    BSTIterator bSTIterator = BSTIterator(root);
    while(bSTIterator.hasNext()){
        cout<<bSTIterator.next()<<endl;
    }
}

【代码二】

class BSTIterator {
    stack<TreeNode *> myStack;
public:
    BSTIterator(TreeNode *root) {
        pushAll(root);
    }

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

    /** @return the next smallest number */
    int next() {
        TreeNode *tmpNode = myStack.top();
        myStack.pop();
        pushAll(tmpNode->right);
        return tmpNode->val;
    }

private:
    void pushAll(TreeNode *node) {
        for (; node != NULL; myStack.push(node), node = node->left);
    }
};