LeetCode173-Binary Search Tree Iterator

女爷i 2022-08-04 12:48 23阅读 0赞

**LeetCode 173 : Binary Search Tree Iterator**

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

来源： [https://leetcode.com/problems/binary-search-tree-iterator/][https_leetcode.com_problems_binary-search-tree-iterator]

**问题描述**：

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

调用next()会返回BST中下一个最小的数字。

注意：next()和hasNext()应该满足平均O(1)时间复杂度和O(h)空间复杂度，其中h是树的高度。

**解题思路**：

创建一个栈，从根节点开始，每次迭代地将根节点的左孩子压入栈，直到左孩子为空为止。

调用next()方法时，弹出栈顶，如果被弹出的元素拥有右孩子，则以右孩子为根，将其左孩子迭代压栈。

这里从 [http://yuanhsh.iteye.com/blog/2173429][http_yuanhsh.iteye.com_blog_2173429] 这篇文章这里借了两张图，很好的讲述了解题思路。

![BinarySearchTreeIterator.png][]  
![BinarySearchTreeIterator2.png][]

**源代码**：

/**
     * Definition for binary tree
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class BSTIterator {
    
        private Stack<TreeNode> nodeStack;
        public BSTIterator(TreeNode root) {
            nodeStack = new Stack<TreeNode>();
            while(null != root){
                nodeStack.push(root);
                root = root.left;
            }
        }
        /** @return whether we have a next smallest number */
        public boolean hasNext() {
           return !nodeStack.isEmpty();
        }
        /** @return the next smallest number */
        public int next() {
            TreeNode node = nodeStack.pop();
            int result = node.val;
            if(null != node.right){
                node = node.right;
                while(null != node){
                    nodeStack.push(node);
                    node = node.left;
                }
            }
            return result;
        }
    }
    /**
     * Your BSTIterator will be called like this:
     * BSTIterator i = new BSTIterator(root);
     * while (i.hasNext()) v[f()] = i.next();
     */

[https_leetcode.com_problems_binary-search-tree-iterator]: https://leetcode.com/problems/binary-search-tree-iterator/
[http_yuanhsh.iteye.com_blog_2173429]: http://yuanhsh.iteye.com/blog/2173429
[BinarySearchTreeIterator.png]: http://7xionv.com1.z0.glb.clouddn.com/phn/arithmetic/BinarySearchTreeIterator.png
[BinarySearchTreeIterator2.png]: http://7xionv.com1.z0.glb.clouddn.com/phn/arithmetic/BinarySearchTreeIterator2.png