Leetcode 173. 二叉搜索树迭代器

题目链接

https://leetcode.com/problems/binary-search-tree-iterator/description/

题目描述

实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。

调用 next() 将返回二叉搜索树中的下一个最小的数。

注意: next() 和hasNext() 操作的时间复杂度是O(1)，并使用 O(h) 内存，其中 h 是树的高度。

题解

代码

/**

 * Definition for binary tree

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode(int x) { val = x; }

 * }

 */

public class BSTIterator {

    private Stack<TreeNode> stack = new Stack<>();

    public BSTIterator(TreeNode root) {

        pushAll(root);

    }

    /** @return whether we have a next smallest number */

    public boolean hasNext() {

        return !stack.isEmpty();

    }

    /** @return the next smallest number */

    public int next() {

        TreeNode tmpNode = stack.pop();

        pushAll(tmpNode.right);

        return tmpNode.val;

    }

    private void pushAll(TreeNode node) {

        for (; node != null; stack.push(node), node = node.left);

    }

}

/**

 * Your BSTIterator will be called like this:

 * BSTIterator i = new BSTIterator(root);

 * while (i.hasNext()) v[f()] = i.next();

 */

巴特西

Leetcode 173. 二叉搜索树迭代器

题目链接

题目描述

题解

代码

最新文章

热门文章