二叉搜索树的遍历,其实也就是数的中序遍历。可以用迭代的方法。
class BSTIterator { public: int pos; vector<TreeNode *> treeNodeStack;</p> <pre><code>void buildStack(TreeNode *node) { if (node == NULL) { return; } else { if (NULL != node-&gt;left) { buildStack(node-&gt;left); } treeNodeStack.push_back(node); if (NULL != node-&gt;right) { buildStack(node-&gt;right); } } } BSTIterator(TreeNode *root) { pos = 0; treeNodeStack.clear(); buildStack(root); } /** @return whether we have a next smallest number */ bool hasNext() { return treeNodeStack.size() &gt; pos; } /** @return the next smallest number */ int next() { return treeNodeStack[pos++]-&gt;val; } </code></pre> <p>};