題目描述

實(shí)現(xiàn)一個(gè)二叉搜索樹(shù)迭代器，使用二叉搜索樹(shù)的根節(jié)點(diǎn)初始化迭代器。
調(diào)用 next() 將返回二叉搜索樹(shù)中的下一個(gè)最小的數(shù)。

示例

背景

二叉搜索樹(shù)：若它的左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值； 若它的右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值； 它的左、右子樹(shù)也分別為二叉搜索樹(shù)。
簡(jiǎn)單來(lái)說(shuō)就是所有節(jié)點(diǎn)都遵循：左節(jié)點(diǎn)<根節(jié)點(diǎn)<右節(jié)點(diǎn)

已知條件

TreeNode，其中只有左節(jié)點(diǎn)left和又節(jié)點(diǎn)right

思路

由于二叉搜索樹(shù)的特性，最小的節(jié)點(diǎn)一定是最“左”的節(jié)點(diǎn)，第二小的節(jié)點(diǎn)一定是最左節(jié)點(diǎn)的根節(jié)點(diǎn)，所以按照中序遍歷的方式即可得到從小到大的序列。
工具：棧
方法：從根節(jié)點(diǎn)開(kāi)始，將根節(jié)點(diǎn)及其所有左節(jié)點(diǎn)依次入棧，每次調(diào)用next時(shí)，從棧頂出一個(gè)節(jié)點(diǎn)，此節(jié)點(diǎn)即為當(dāng)前最小的節(jié)點(diǎn)，暫且稱(chēng)為節(jié)點(diǎn)A
考慮問(wèn)題：

1. 如果A是葉子節(jié)點(diǎn)，那個(gè)下一個(gè)最小節(jié)點(diǎn)一定是A的父節(jié)點(diǎn)，此時(shí)直接將A出棧即可
   2.由于前邊把所有左節(jié)點(diǎn)都入棧了，所以L節(jié)點(diǎn)不可能有左節(jié)點(diǎn)，但是可能有右節(jié)點(diǎn)，如果有右節(jié)點(diǎn)，不妨稱(chēng)為R，那么當(dāng)前棧頂節(jié)點(diǎn)（不妨稱(chēng)為P）一定比R大，因?yàn)長(zhǎng)是P的左節(jié)點(diǎn)，所以P>L及L的所有子節(jié)點(diǎn)，所以下一個(gè)最小的節(jié)點(diǎn)一定在R及R的子節(jié)點(diǎn)中，現(xiàn)在問(wèn)題變?yōu)檎业絉及R子節(jié)點(diǎn)中最小的節(jié)點(diǎn)，這個(gè)問(wèn)題就是當(dāng)前在解決的問(wèn)題，只不過(guò)規(guī)模小一點(diǎn)而已，所以還是按照前面做的：把R及R的左節(jié)點(diǎn)依次入棧，此時(shí)棧頂?shù)墓?jié)點(diǎn)一定又是最小的節(jié)點(diǎn)

實(shí)現(xiàn)

class BSTIterator(var root: TreeNode?) {
    val stack = LinkedList<TreeNode>()

    init {
        root?.let {
            pushData(it)
        }
    }

    fun pushData(treeNode: TreeNode?) {
        treeNode?.let {
            stack.push(it) //將父節(jié)點(diǎn)入棧
            var node: TreeNode = it
            while (node.left != null) {//循環(huán)遍歷父節(jié)點(diǎn)的所有左節(jié)點(diǎn)，依次入棧
                stack.push(node.left)
                node = node.left!!
            }
        }
    }

    //迭代器方法
    fun next(): Int {
        var node = stack.pop() //棧頂節(jié)點(diǎn)一定是最小的節(jié)點(diǎn)
        pushData(node.right)//如果當(dāng)前棧頂節(jié)點(diǎn)的右節(jié)點(diǎn)不為空，那么需要把右節(jié)點(diǎn)中的所有左節(jié)點(diǎn)再次入棧，保證棧頂節(jié)點(diǎn)一定是最小的節(jié)點(diǎn)
        return node.value
    }

    //迭代器方法
    fun hasNext(): Boolean {
        return !stack.isEmpty() //棧為空則遍歷完了
    }

    class TreeNode(var value: Int) {
        var left: TreeNode? = null
        var right: TreeNode? = null
    }
}