題目

請實現(xiàn)二叉搜索樹的迭代器BSTIterator，它主要有如下3個函數(shù)。

• 構(gòu)造函數(shù)：輸入二叉搜索樹的根節(jié)點初始化該迭代器。
• 函數(shù)next：返回二叉搜索樹中下一個最小的節(jié)點的值。
• 函數(shù)hasNext：返回二叉搜索樹是否還有下一個節(jié)點。

分析

如果對二叉樹的中序遍歷的迭代代碼足夠熟悉，我們就會注意到中序遍歷的迭代代碼中有一個while循環(huán)，循環(huán)的條件為true時循環(huán)體每執(zhí)行一次就遍歷二叉樹的一個節(jié)點。當(dāng)while循環(huán)的條件為false時，二叉樹中的所有節(jié)點都已遍歷完。因此，中序遍歷的迭代代碼中的while循環(huán)可以看成迭代器hasNext的判斷條件，而while循環(huán)體內(nèi)執(zhí)行的操作就是函數(shù)next執(zhí)行的操作。

解

public class BSTIterator {TreeNode cur;Stack<TreeNode> stack;public BSTIterator(TreeNode root) {cur = root;stack = new Stack<>();}public boolean hasNext() {return cur != null || !stack.isEmpty();}public int next() {while (cur != null) {stack.push(cur);cur = cur.left;}cur = stack.pop();int val = cur.val;cur = cur.right;return val;}
}