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;

        }

    }

};

巴特西

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

86-二叉查找树迭代器

样例

挑战

标签

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

code

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

code

最新文章

热门文章