[Leetcode - Tree] Binary Search Tree Iterator

jsyzchen 发布于2019-08-16 10:26 / 886人阅读

摘要：解题思路对于二叉搜索树，我们很容易会想到使用栈和队列来解决问题，本题是要求实现一个对二叉搜索树的遍历器，要求每次可以返回最小的节点值，我们使用栈。

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.

1.解题思路

对于二叉搜索树，我们很容易会想到使用栈和队列来解决问题，本题是要求实现一个对二叉搜索树的遍历器，要求每次可以返回最小的节点值，我们使用栈。
1）hasnext()，很容易实现，只要判断栈是否为空；
2）BSTIterator构造函数，我们可以从根节点开始，陆续将左节点压入栈中，这样迭代器构造完后，栈顶元素就是最小的；
3）next()，每次pop出的栈顶元素，该元素肯定不会有左节点，但是我们需要判断其是否有右节点，如果有，我们要将右节点压入栈中，而且还要继续将右节点下面的所有左节点压入栈中，这样才能保证栈顶元素就是最小的。

2.代码

public class BSTIterator {
    Stack s=new Stack();
    public BSTIterator(TreeNode root) {
        if(root!=null){
            s.push(root);
            pushLeft(root);
        }
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !s.empty();
    }

    /** @return the next smallest number */
    public int next() {
        TreeNode node=s.pop();
        int value=node.val;
        TreeNode rnode=node.right;
        if(rnode!=null){
            s.push(rnode);
            pushLeft(rnode);
        }
        return value;
    }
    private void pushLeft(TreeNode root){
        TreeNode node=root.left;
        while(node!=null){
                s.push(node);
                node=node.left;
            }
    }
}

云服务器 GPU云服务器 binary-search-tree binary-tree binary-search tree

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/69789.html

[Leetcode] Binary Search Tree Iterator 二叉搜素树迭代器

摘要：代码先找到第一个节点，并把路径入栈栈为空时不再有下一个栈顶是待返回元素如果该元素有右节点，把它的右节点及右节点的所有左边节点都压入栈中 Binary Search Tree Iterator 最新更新：https://yanjia.me/zh/2019/02/... Implement an iterator over a binary search tree (BST). Your...

shixinzhang 2019-08-14 12:36 评论0 收藏0
[LintCode] Binary Search Tree Iterator

摘要：建立一个堆栈，先将最左边的结点从大到小压入栈，这样的话，为了实现迭代即返回下一个的函数就要考虑右边的结点。如此，实现函数。 Problem Design an iterator over a binary search tree with the following rules: Elements are visited in ascending order (i.e. an in-o...

silencezwm 2019-08-14 15:33 评论0 收藏0
leetcode98. Validate Binary Search Tree

摘要：题目要求检验二叉查找树是否符合规则。二叉查找树是指当前节点左子树上的值均比其小，右子树上的值均比起大。因此在这里我们采用栈的方式实现中序遍历，通过研究中序遍历是否递增来判断二叉查找树是否符合规则。题目要求 Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is...

codercao 2019-08-15 10:56 评论0 收藏0
leetcode98. Validate Binary Search Tree

摘要：题目要求检验二叉查找树是否符合规则。二叉查找树是指当前节点左子树上的值均比其小，右子树上的值均比起大。因此在这里我们采用栈的方式实现中序遍历，通过研究中序遍历是否递增来判断二叉查找树是否符合规则。题目要求 Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is...

AlphaWatch 2019-08-15 10:56 评论0 收藏0
leetcode98. Validate Binary Search Tree

摘要：题目要求判断一个树是否是二叉查找树。二叉查找树即满足当前节点左子树的值均小于当前节点的值，右子树的值均大于当前节点的值。思路一可以看到，对二叉查找树的中序遍历结果应当是一个递增的数组。这里我们用堆栈的方式实现中序遍历。题目要求 given a binary tree, determine if it is a valid binary search tree (BST). Assu...

songze 2019-08-15 10:56 评论0 收藏0