Binary Search Tree Iterator(Hard)

题目描述

Design an iterator over a binary search tree with the following rules: Elements are visited in ascending order (i.e. an in-order traversal) next() and hasNext() queries run in O(1) time in average.

Example

For the following binary search tree, in-order traversal by using iterator is [1, 6, 10, 11, 12]

   10
 /    \
1      11
 \       \
  6       12

题目链接

解题思路

设计Iterator和非递归遍历二叉树很相似。这里有篇不错的讲解Here。 一般需要O(n)的空间复杂度和每次操作均摊O(1)的时间复杂度。

如果要改进空间复杂度，可以使用Morris Traversal，可以参考这里Here 其空间复杂度可以做到O（1）。这种方法利用了叶节点的右指针。

参考代码

普通方法

/**
 * 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()) {
 *    TreeNod * node = iterator.next();
 *    do something for node
 */
class BSTIterator {
public:
    //@param root:The root of binary tree.
    BSTIterator(TreeNode *root) {
        // write your code here
        TreeNode *ptr = root;
        while (ptr != nullptr) {
            myStack.push(ptr);
            ptr = ptr->left;

    }

    //@return: True if there has next node, or false
    bool hasNext() {
        return myStack.empty() ? false : true;
        // write your code here
    }

    //@return: return next node
    TreeNode* next() {
        // write your code here
        TreeNode *top = myStack.top();
        myStack.pop();
        TreeNode *ptr = top;
        if (ptr->right != nullptr) {
            ptr = ptr->right;
            while (ptr != nullptr) {
                myStack.push(ptr);
                ptr = ptr->left;
            }
        }
        return top;
    }

    stack<TreeNode *> myStack;
};

Morris Traversal

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

/** @return whether we have a next smallest number */
bool hasNext() {
    return p != NULL;
}

/** @return the next smallest number */
int next() {
    TreeNode *tmp;
    int ret;
    while(p) {
        if (p->left == NULL) {  
            ret = p->val;
            p = p->right;
            break;
        }  
        else {  
            tmp = p->left;  
            while (tmp->right != NULL && tmp->right != p)  
                tmp = tmp->right;  
            if (tmp->right == NULL) {  
                tmp->right = p;  
                p = p->left;  
            }  
            else {
                ret = p->val;
                tmp->right = NULL;  
                p = p->right;
                break;
            }  
        }  
    }

    return ret;
}

TreeNode *p;
};