lintcode-86-二叉查找树迭代器

86-二叉查找树迭代器

设计实现一个带有下列属性的二叉查找树的迭代器：
元素按照递增的顺序被访问（比如中序遍历）
next()和hasNext()的询问操作要求均摊时间复杂度是O(1)

样例

对于下列二叉查找树，使用迭代器进行中序遍历的结果为 [1, 6, 10, 11, 12]

挑战

额外空间复杂度是O(h)，其中h是这棵树的高度
Super Star：使用O(1)的额外空间复杂度

标签

二叉树 二叉查找树 LintCode 版权所有 非递归 谷歌 领英 脸书

方法一（空间复杂度O(n)，n为树的节点数）：

使用数组保存树的中序遍历的结果

code

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 * Example of iterate a tree:
 * BSTIterator iterator = BSTIterator(root);
 * while (iterator.hasNext()) {
 *    TreeNode * node = iterator.next();
 *    do something for node
 */
class BSTIterator {
public:
    vector<TreeNode *> inorder;
    int current;

    //@param root: The root of binary tree.
    BSTIterator(TreeNode *root) {
        // write your code here
        inorder = inorderTraversal(root);
        current = 0;
    }

    //@return: True if there has next node, or false
    bool hasNext() {
        // write your code here
        if(current == inorder.size()) {
            return false;
        }
        else {
            return true;
        }
    }
    
    //@return: return next node
    TreeNode* next() {
        // write your code here
        return inorder[current++];
    }

    vector<TreeNode *> inorderTraversal(TreeNode *root) {
        vector<TreeNode *> order;

        if(root == NULL) {
            return vector<TreeNode *>();
        }

        stack<TreeNode *> s;
        TreeNode *p = root;
        while(p != NULL || !s.empty()) {
            while(p != NULL) {
                s.push(p);
                p = p->left;
            }
            if(!s.empty()) {
                p = s.top();
                order.push_back(p);
                s.pop();
                p = p->right;
            }
        } 
        return order;
    }
};

方法二（空间复杂度O(h)，h为树的高度）：

参考博客http://blog.csdn.net/smile_watermelon/article/details/47280679

code

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 * Example of iterate a tree:
 * BSTIterator iterator = BSTIterator(root);
 * while (iterator.hasNext()) {
 *    TreeNode * node = iterator.next();
 *    do something for node
 */
class BSTIterator {
public:
   
    stack<TreeNode *> inorder;

    //@param root: The root of binary tree.
    BSTIterator(TreeNode *root) {
        // write your code here
        putIntoStack(root);
    }

    //@return: True if there has next node, or false
    bool hasNext() {
        // write your code here
        return !inorder.empty();
    }
    
    //@return: return next node
    TreeNode* next() {
        // write your code here 
        TreeNode *current = inorder.top();
        TreeNode *temp = current;
        inorder.pop();

        putIntoStack(current->right);

        return current;
    }

    void putIntoStack(TreeNode *root) {
        TreeNode *node = root;
        while(node != NULL) {
            inorder.push(node);
            node = node->left;
        }
    }
};