博文中会简要介绍Leetcode P0173题目分析及解题思路。
“Binary Search Tree Iterator”是一道比较经典的设计题。题目要求设计一个二叉搜索树的迭代器，每次next()可以得到该二叉搜索树中序遍历的下一个结点的值。
这道题其实本质上就是对二叉搜索树的中序遍历。一般有两种解法，第一种在初始化的时候不断遍历左孩子结点，将这些结点放入栈中，然后每次获取下一个结点值的时候，在返回结果（栈顶结点的值）之前获取该结点的右孩子结点的所有左孩子结点，并将其压入栈内。
第二种解法则是一开始就中序遍历一遍二叉搜索树，将所有的结点值按序存入数组，将二叉搜索树的迭代器转化为数组的迭代器。
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.
第一种解法的初始化的最坏时间复杂度是O(logn)，而next()的最坏时间复杂度同样是O(logn)。它的空间复杂度则是O(1)。需要强调的一点是，若对这个解法进行均摊分析，将所有结点值用next()遍历一遍其实是O(n)的时间复杂度，所以这里对单独的next()操作的时间复杂度分析用的是最坏情况。而这种解法本质上就是用迭代的方式对二叉搜索数进行中序遍历。
以下是Java的题解代码实现。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class BSTIterator {
private Deque<TreeNode> stack = new LinkedList<>();
private TreeNode curr = null;
public BSTIterator(TreeNode root) {
// Add the left subtree
this.add(root);
}
/** @return the next smallest number */
public int next() {
TreeNode next = stack.pollFirst();
// Check the right subtree, whose left subtree will be added
this.add(next.right);
return next.val;
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
return !stack.isEmpty();
}
private void add(TreeNode root) {
curr = root;
while (curr != null) {
stack.offerFirst(curr);
curr = curr.left;
}
}
}
/**
* Your BSTIterator object will be instantiated and called as such:
* BSTIterator obj = new BSTIterator(root);
* int param_1 = obj.next();
* boolean param_2 = obj.hasNext();
*/
第二种解法的空间复杂度是O(n)，初始化的时间复杂度是O(n)，但next()的时间复杂度是O(1)。这个解法本质上就是得到给定的二叉搜素树的中序遍历结果，并用数组存储这个结果，将对二叉搜索树的迭代转为对数组的迭代。
不过从设计的角度来思考，对于用户而言其实没有本质区别。这就是“封装”的思想，即只要实现了需求的功能，内部的具体实现机制其实是黑盒子，用户无需知晓。
以下是C++的题解代码实现。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class BSTIterator {
public:
BSTIterator(TreeNode* root) {
stack<TreeNode*> node_stack;
TreeNode *curr = root;
while (curr || !node_stack.empty()) {
while (curr) {
node_stack.push(curr);
curr = curr->left;
}
curr = node_stack.top();
this->data.push_back(curr->val);
node_stack.pop();
curr = curr->right;
}
}
/** @return the next smallest number */
int next() {
return this->data[this->iterator++];
}
/** @return whether we have a next smallest number */
bool hasNext() {
return (iterator < this->data.size());
}
private:
vector<int> data;
int iterator = 0;
};
/**
* Your BSTIterator object will be instantiated and called as such:
* BSTIterator* obj = new BSTIterator(root);
* int param_1 = obj->next();
* bool param_2 = obj->hasNext();
*/