173. 二叉搜索树迭代器

题意：

解题思路：

next()方法做两件事：
1. 把栈顶节点出栈，并把节点值返回
2. 把栈顶节点右子树的最左侧分支入栈

PHP代码实现：

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) { $this->val = $value; }
 * }
 */
class BSTIterator {
    /**
     * @param TreeNode $root
     */
    private $stack = [];
    function __construct($root) {
        while ($root != null) {
            $this->stack[] = $root;
            $root = $root->left;
        }
    }
    /**
     * @return the next smallest number
     * @return Integer
     */
    function next() {
        $root = array_pop($this->stack);
        $val = $root->val;
        $root = $root->right;
        while ($root != null) {
            $this->stack[] = $root;
            $root = $root->left;
        }
        return $val;
    }
    /**
     * @return whether we have a next smallest number
     * @return Boolean
     */
    function hasNext() {
        return !empty($this->stack);
    }
}
/**
 * Your BSTIterator object will be instantiated and called as such:
 * $obj = BSTIterator($root);
 * $ret_1 = $obj->next();
 * $ret_2 = $obj->hasNext();
 */

go代码实现：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
type BSTIterator struct {
    stack []*TreeNode
}
func Constructor(root *TreeNode) BSTIterator {
    BST := []*TreeNode{}
    for root != nil {
        BST = append(BST, root)
        root = root.Left
    }
    return BSTIterator {
        stack: BST,
    }
}
/** @return the next smallest number */
func (this *BSTIterator) Next() int {
    n := len(this.stack)
    cur := this.stack[n - 1]
    this.stack = this.stack[:n-1]
    root := cur.Right
    for root != nil {
        this.stack = append(this.stack, root)
        root = root.Left
    }
    return cur.Val
}
/** @return whether we have a next smallest number */
func (this *BSTIterator) HasNext() bool {
    return len(this.stack) > 0
}
/**
 * Your BSTIterator object will be instantiated and called as such:
 * obj := Constructor(root);
 * param_1 := obj.Next();
 * param_2 := obj.HasNext();
 */