1.題目描述
劍指 Offer II 055. 二叉搜索樹(shù)迭代器
實(shí)現(xiàn)一個(gè)二叉搜索樹(shù)迭代器類(lèi)BSTIterator 懈凹，表示一個(gè)按中序遍歷二叉搜索樹(shù)（BST）的迭代器：
BSTIterator(TreeNode root) 初始化 BSTIterator 類(lèi)的一個(gè)對(duì)象惫企。BST 的根節(jié)點(diǎn) root 會(huì)作為構(gòu)造函數(shù)的一部分給出嫉称。指針應(yīng)初始化為一個(gè)不存在于 BST 中的數(shù)字，且該數(shù)字小于 BST 中的任何元素。
boolean hasNext() 如果向指針右側(cè)遍歷存在數(shù)字，則返回 true ；否則返回 false 泊交。
int next()將指針向右移動(dòng)，然后返回指針處的數(shù)字柱查。
注意廓俭，指針初始化為一個(gè)不存在于 BST 中的數(shù)字，所以對(duì) next() 的首次調(diào)用將返回 BST 中的最小元素唉工。
可以假設(shè) next() 調(diào)用總是有效的研乒，也就是說(shuō)，當(dāng)調(diào)用 next() 時(shí)淋硝，BST 的中序遍歷中至少存在一個(gè)下一個(gè)數(shù)字雹熬。
示例：
輸入
inputs = ["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
inputs = [[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
輸出
[null, 3, 7, true, 9, true, 15, true, 20, false]
解釋
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next(); // 返回 3
bSTIterator.next(); // 返回 7
bSTIterator.hasNext(); // 返回 True
bSTIterator.next(); // 返回 9
bSTIterator.hasNext(); // 返回 True
bSTIterator.next(); // 返回 15
bSTIterator.hasNext(); // 返回 True
bSTIterator.next(); // 返回 20
bSTIterator.hasNext(); // 返回 False
2.解題思路與代碼
2.1 解題思路
編寫(xiě)一個(gè)二叉搜索樹(shù)的迭代器，使迭代器按照從小到大的順序返回節(jié)點(diǎn)值谣膳。我們知道二叉搜索樹(shù)的中序遍歷得到的結(jié)果就是從小到大以此遞增的竿报，可以利用這一特性來(lái)完成題目。首先我們構(gòu)建一個(gè)列表 list 存放二叉搜索樹(shù)中序遍歷經(jīng)過(guò)的節(jié)點(diǎn)继谚，然后在構(gòu)造方法中對(duì)該二叉搜索樹(shù)進(jìn)行中序遍歷烈菌，并放入列表 list 中。
List<TreeNode> list;
int index = -1;
public BSTIterator(TreeNode root) {
list = new ArrayList<>();
process(root);
}
public void process(TreeNode node) {
if (node == null) {
return;
}
process(node.left);
list.add(node);
process(node.right);
}
這里還需要一個(gè) index 變量來(lái)遍歷該列表花履，以模擬迭代器芽世。我們需要完成迭代器的 next() 和 hasNext() 兩個(gè)方法，next() 方法要獲取 index 角標(biāo)的下一位元素诡壁，即 list.get(++index)济瓢，而 hasNext 方法直接判斷 index+1 是否小于列表長(zhǎng)度即可。
public int next() {
return list.get(++index).val;
}
public boolean hasNext() {
return index + 1 < list.size();
}
2.2 代碼
class BSTIterator {
List<TreeNode> list;
int index = -1;
public BSTIterator(TreeNode root) {
list = new ArrayList<>();
process(root);
}
public void process(TreeNode node) {
if (node == null) {
return;
}
process(node.left);
list.add(node);
process(node.right);
}
public int next() {
return list.get(++index).val;
}
public boolean hasNext() {
return index + 1 < list.size();
}
}
2.3 測(cè)試結(jié)果
通過(guò)測(cè)試
3.總結(jié)
- 利用二叉搜索樹(shù)中序遍歷結(jié)果是增序特性解答
- 也可以直接使用列表的迭代器解答
