二叉搜索樹(shù)迭代器

題目描述：實(shí)現(xiàn)一個(gè)二叉搜索樹(shù)迭代器類BSTIterator ，表示一個(gè)按中序遍歷二叉搜索樹(shù)（BST）的迭代器：

• BSTIterator(TreeNode root) 初始化 BSTIterator 類的一個(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ù)字。

示例說(shuō)明請(qǐng)見(jiàn)LeetCode官網(wǎng)。

來(lái)源：力扣（LeetCode） ??

鏈接：https://leetcode-cn.com/problems/binary-search-tree-iterator/ ??

著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

解法一：中序遍歷

首先，在BSTIterator內(nèi)聲明一個(gè)List為values用來(lái)存二叉樹(shù)的節(jié)點(diǎn)值，在構(gòu)造方法內(nèi)通過(guò)中序遍歷的方式將節(jié)點(diǎn)值初始化到values中。

然后，聲明一個(gè)index標(biāo)識(shí)當(dāng)前位置，next()方法和hasNext()方法的實(shí)現(xiàn)即依賴于index和values進(jìn)行判斷即可。

【每日寄語(yǔ)】 中流砥柱，力挽狂瀾，具天才，立大業(yè)，拯斯民于衽席，奠國(guó)運(yùn)如磐石，非大英雄無(wú)以任之。