Tree - 173. Binary Search Tree Iterator

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.

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

Example:

BSTIterator iterator = new BSTIterator(root);
iterator.next();    // return 3
iterator.next();    // return 7
iterator.hasNext(); // return true
iterator.next();    // return 9
iterator.hasNext(); // return true
iterator.next();    // return 15
iterator.hasNext(); // return true
iterator.next();    // return 20
iterator.hasNext(); // return false

思路：

题目要求写一个bst的迭代器，实现两个接口，输出树中目前最小的值，和树中目前有没有下一个节点。仔细分析会发现，由于bst的根节点比左边的大比右边的小，要从小到达输出，明显就是中序遍历来做这道题，这里采用容器list来当stack，当然也可以自己使用切片和一个栈顶指针来实现一个栈。

代码：

go：

/**

 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

type BSTIterator struct {
    Stack *list.List
}


func Constructor(root *TreeNode) BSTIterator {
    bsti := BSTIterator{Stack:list.New()}
    bsti.push(root)
    return bsti
}


/** @return the next smallest number */
func (this *BSTIterator) Next() int {
    e := this.Stack.Back()
    cur := e.Value.(*TreeNode)
    this.Stack.Remove(e)

    this.push(cur.Right)
    return cur.Val
}


/** @return whether we have a next smallest number */
func (this *BSTIterator) HasNext() bool {
    return this.Stack.Len() != 0    
}

func (this *BSTIterator) push(node *TreeNode) {
    for node != nil {
        this.Stack.PushBack(node)
        node = node.Left
    }
}


/**
 * Your BSTIterator object will be instantiated and called as such:
 * obj := Constructor(root);
 * param_1 := obj.Next();
 * param_2 := obj.HasNext();
 */