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

shixinzhang 发布于2019-08-14 12:36 / 2787人阅读

摘要：代码先找到第一个节点，并把路径入栈栈为空时不再有下一个栈顶是待返回元素如果该元素有右节点，把它的右节点及右节点的所有左边节点都压入栈中

Binary Search Tree Iterator 最新更新：https://yanjia.me/zh/2019/02/...

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.

栈法 复杂度

时间 O(N) 空间 O(1)

思路

这道题和Inorder Successor in BST很像，区别在于Successor那题是给定节点求下一个，而这题是要做一个迭代器，返回当前指向的值，其实就是求上次返回的节点的下一个，本质是一样的。题目要求最多只能用O(H)的空间，所以思路也和那题一样，用一个Stack记录从根节点到当前节点的路径。next的时候就返回Stack最上面的元素。不过拿出最上面的元素后，我们还要看一下这个被返回的元素是否有右节点，如果有的话，就把它的右节点及右节点的所有左边节点都压入栈中。另外，初始化栈时，我们要找到最左边的节点，也就是中序遍历的第一个节点，并把根到第一个节点的路径都压入栈。

这题还可以结合Binary Tree Inorder Traverse的迭代做法一起理解。他们的共同点都是用一个栈，将最左边的节点都压入栈。

代码

public class BSTIterator {
    
    Stack stk;

    public BSTIterator(TreeNode root) {
        stk = new Stack();
        // 先找到第一个节点，并把路径入栈
        while(root != null){
            stk.push(root);
            root = root.left;
        }
    }

    public boolean hasNext() {
        // 栈为空时不再有下一个
        return !stk.isEmpty();
    }

    public int next() {
        // 栈顶是待返回元素
        TreeNode curr = stk.pop();
        int res = curr.val;
        // 如果该元素有右节点，把它的右节点及右节点的所有左边节点都压入栈中
        if(curr.right != null){
            curr = curr.right;
            while(curr != null){
                stk.push(curr);
                curr = curr.left;
            }
        }
        return res;
    }
}

云服务器 GPU云服务器二叉搜素树 binary-search-tree binary-tree binary-search

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

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

[Leetcode - Tree] Binary Search Tree Iterator

摘要：解题思路对于二叉搜索树，我们很容易会想到使用栈和队列来解决问题，本题是要求实现一个对二叉搜索树的遍历器，要求每次可以返回最小的节点值，我们使用栈。 Binary Search Tree IteratorImplement an iterator over a binary search tree (BST). Your iterator will be initialized with...

jsyzchen 2019-08-16 10:26 评论0 收藏0
[Leetcode] Closest Binary Search Tree Value 最近二叉搜索

摘要：递归法复杂度时间空间思路根据二叉树的性质，我们知道当遍历到某个根节点时，最近的那个节点要么是在子树里面，要么就是根节点本身。因为我们知道离目标数最接近的数肯定在二叉搜索的路径上。 Closest Binary Search Tree Value I Given a non-empty binary search tree and a target value, find the va...

AlphaWallet 2019-08-14 12:37 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0
leetcode讲解--94. Binary Tree Inorder Traversal

摘要：题目地址嗯，经典的题目，中序遍历二叉树。代码如下中序遍历先序遍历后序遍历是不是简单的不要不要的，递归就是这么美。右孩子后压栈全部释放出来嗯，总的来说用迭代遍历确实烧脑，没什么性能上的特殊需求还是用递归写法吧，对程序员友好哦。 94. Binary Tree Inorder Traversal Given a binary tree, return the inorder travers...

henry14 2019-07-25 11:22 评论0 收藏0
[Leetcode] Validate Binary Search Tree 验证二叉搜索树

摘要：注意这里的结构和不同的二叉树遍历一样，如果到空节点就返回，否则递归遍历左节点和右节点。唯一不同是加入了和，所以要在递归之前先判断是否符合和的条件。代码如果该节点大于上限返回假如果该节点小于下限返回假递归判断左子树和右子树 Validate Binary Search Tree Given a binary tree, determine if it is a valid binary...

fuchenxuan 2019-08-14 12:40 评论0 收藏0