每日算法题—二叉搜索树迭代器

题目描述

实现一个二叉搜索树迭代器，使用二叉搜索树的根节点初始化迭代器。
调用 next() 将返回二叉搜索树中的下一个最小的数。

示例

背景

二叉搜索树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉搜索树。
简单来说就是所有节点都遵循：左节点<根节点<右节点

已知条件

TreeNode，其中只有左节点left和又节点right

思路

由于二叉搜索树的特性，最小的节点一定是最“左”的节点，第二小的节点一定是最左节点的根节点，所以按照中序遍历的方式即可得到从小到大的序列。
工具：栈
方法：从根节点开始，将根节点及其所有左节点依次入栈，每次调用next时，从栈顶出一个节点，此节点即为当前最小的节点，暂且称为节点A
考虑问题：

1. 如果A是叶子节点，那个下一个最小节点一定是A的父节点，此时直接将A出栈即可
   2.由于前边把所有左节点都入栈了，所以L节点不可能有左节点，但是可能有右节点，如果有右节点，不妨称为R，那么当前栈顶节点（不妨称为P）一定比R大，因为L是P的左节点，所以P>L及L的所有子节点，所以下一个最小的节点一定在R及R的子节点中，现在问题变为找到R及R子节点中最小的节点，这个问题就是当前在解决的问题，只不过规模小一点而已，所以还是按照前面做的：把R及R的左节点依次入栈，此时栈顶的节点一定又是最小的节点

实现

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

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

    fun pushData(treeNode: TreeNode?) {
        treeNode?.let {
            stack.push(it) //将父节点入栈
            var node: TreeNode = it
            while (node.left != null) {//循环遍历父节点的所有左节点，依次入栈
                stack.push(node.left)
                node = node.left!!
            }
        }
    }

    //迭代器方法
    fun next(): Int {
        var node = stack.pop() //栈顶节点一定是最小的节点
        pushData(node.right)//如果当前栈顶节点的右节点不为空，那么需要把右节点中的所有左节点再次入栈，保证栈顶节点一定是最小的节点
        return node.value
    }

    //迭代器方法
    fun hasNext(): Boolean {
        return !stack.isEmpty() //栈为空则遍历完了
    }

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