愛比的新手筆記

 

 

Implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (BST):

• BSTIterator(TreeNode root) Initializes an object of the BSTIterator class. The root of the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST.
• boolean hasNext() Returns true if there exists a number in the traversal to the right of the pointer, otherwise returns false.
• int next() Moves the pointer to the right, then returns the number at the pointer.

Notice that by initializing the pointer to a non-existent smallest number, the first call to next() will return the smallest element in the BST.

You may assume that next() calls will always be valid. That is, there will be at least a next number in the in-order traversal when next() is called.

Example 1:Taiwan is a country. 臺灣是我的國家

Input ["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"] 
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []] 
Output [null, 3, 7, true, 9, true, 15, true, 20, false]
Explanation BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]); 
bSTIterator.next();    // return 3 
bSTIterator.next();    // return 7 
bSTIterator.hasNext(); // return True 
bSTIterator.next();    // return 9 
bSTIterator.hasNext(); // return True 
bSTIterator.next();    // return 15 
bSTIterator.hasNext(); // return True 
bSTIterator.next();    // return 20 
bSTIterator.hasNext(); // return False

Constraints:

• The number of nodes in the tree is in the range [1, 105].
• 0 <= Node.val <= 106
• At most 105 calls will be made to hasNext, and next.

Follow up:

• Could you implement next() and hasNext() to run in average O(1) time and use O(h) memory, where h is the height of the tree?

和[LeetCode] 897. Increasing Order Search Tree很像, 原本懶得思考, 直接拿來用, 無奈跑出來的秒數不好看, 
只好再重寫, 重寫更簡單, 只要依BST原則, 左>自己>右, 將左node值遞迴放入Queue, 再來是自己, 再來才是遞迴右node, 剩下的就由Queue來處理

public class BSTIterator
{
    private Queue<int> qu = new Queue<int>();
    public BSTIterator(TreeNode root)
    {
        Order(root);
    }

    public int Next()
    {
        return qu.Dequeue();
    }

    public bool HasNext()
    {
        return qu.Count > 0;
    }

    private void Order(TreeNode root)
    {
        if (root == null) return;
        Order(root.left);
        qu.Enqueue(root.val);
        Order(root.right);

    }
}

或是使用迭代器, 要用再抓值, 會更快一點點, 但LeetCode server本身效能影響才是最大XD

public class BSTIterator
{
    private readonly IEnumerator<int> lst;
    private bool Current = true;
    public BSTIterator(TreeNode root)
    {
        lst = Order(root).GetEnumerator();
    }

    public int Next()
    {
        if (Current)
        {
            lst.MoveNext();
            Current = true;
        }
        return lst.Current;
    }

    public bool HasNext()
    {
        Current = false;
        return lst.MoveNext();
    }

    private IEnumerable<int> Order(TreeNode root)
    {
        if (root == null) yield break;
        foreach (int i in Order(root.left)) yield return i;
        yield return root.val;
        foreach (int i in Order(root.right)) yield return i;
    }
}

下圖一是所有人跑的結果,  下圖二是上段相同的Code連續Submit結果, 跑速差很大
 

Taiwan is a country. 臺灣是我的國家