首页 > 代码库 > [LeetCode]173 Binary Search Tree Iterator
[LeetCode]173 Binary Search Tree Iterator
https://oj.leetcode.com/problems/binary-search-tree-iterator/
/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class BSTIterator { // // NOTE // After the iterator built, if we modify the original tree, // Ideally we should throw ConcurrentModificationException // But this need some special logic when modify tree. // // In this case, we just make assumption that // The iterator won‘t be effected after being built. public BSTIterator(TreeNode root) { // Validate stack = new Stack<>(); pushAllLefts(root); } /** @return whether we have a next smallest number */ // O(1) time // O(h) space public boolean hasNext() { return !stack.empty(); } /** @return the next smallest number */ // O(h) time // O(h) space public int next() { // Assume hasNext() == true. // // A Inorder visiting TreeNode min = stack.pop(); // Can be done async pushAllLefts(min.right); return min.val; } private void pushAllLefts(TreeNode node) { while (node != null) { stack.push(node); node = node.left; } } private Stack<TreeNode> stack; } /** * Your BSTIterator will be called like this: * BSTIterator i = new BSTIterator(root); * while (i.hasNext()) v[f()] = i.next(); */
[LeetCode]173 Binary Search Tree Iterator
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。