二叉搜索树的遍历，其实也就是数的中序遍历。可以用迭代的方法。

class BSTIterator {
public:
    int pos;
    vector&lt;TreeNode *&gt; treeNodeStack;</p>

<pre><code>void buildStack(TreeNode *node)
{
    if (node == NULL)
    {
        return;
    }
    else
    {
        if (NULL != node-&amp;gt;left)
        {
            buildStack(node-&amp;gt;left);
        }
        treeNodeStack.push_back(node);
        if (NULL != node-&amp;gt;right)
        {
            buildStack(node-&amp;gt;right);
        }
    }
}

BSTIterator(TreeNode *root) {
    pos = 0;
    treeNodeStack.clear();
    buildStack(root);
}

/** @return whether we have a next smallest number */
bool hasNext() {
    return treeNodeStack.size() &amp;gt; pos;
}

/** @return the next smallest number */
int next() {
    return treeNodeStack[pos++]-&amp;gt;val;
}
</code></pre>

<p>};