建设网站之前都需要准备什么问题,建立目录wordpress,营销方案效果评估范文,如何改更wordpress上下文章链接实现一个二叉搜索树迭代器类BSTIterator #xff0c;表示一个按中序遍历二叉搜索树#xff08;BST#xff09;的迭代器#xff1a; BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在…实现一个二叉搜索树迭代器类BSTIterator 表示一个按中序遍历二叉搜索树BST的迭代器 BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字且该数字小于 BST 中的任何元素。 boolean hasNext() 如果向指针右侧遍历存在数字则返回 true 否则返回 false 。 int next()将指针向右移动然后返回指针处的数字。 注意指针初始化为一个不存在于 BST 中的数字所以对 next() 的首次调用将返回 BST 中的最小元素。
你可以假设 next() 调用总是有效的也就是说当调用 next() 时BST 的中序遍历中至少存在一个下一个数字。
示例
输入 [“BSTIterator”, “next”, “next”, “hasNext”, “next”, “hasNext”, “next”, “hasNext”, “next”, “hasNext”] [[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []] 输出 [null, 3, 7, true, 9, true, 15, true, 20, false]
解释 BSTIterator bSTIterator new BSTIterator([7, 3, 15, null, null, 9, 20]); bSTIterator.next(); // 返回 3 bSTIterator.next(); // 返回 7 bSTIterator.hasNext(); // 返回 True bSTIterator.next(); // 返回 9 bSTIterator.hasNext(); // 返回 True bSTIterator.next(); // 返回 15 bSTIterator.hasNext(); // 返回 True bSTIterator.next(); // 返回 20 bSTIterator.hasNext(); // 返回 False
解题思路
使用栈实现中序遍历 当前遍历的节点出栈时将它右节点以及右节点上的所有子节点入栈实现中序遍历
代码
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/class BSTIterator {StackTreeNode stacknew Stack();public BSTIterator(TreeNode root) {while (root!null){stack.add(root);rootroot.left;}}public int next() {TreeNode pop stack.pop();TreeNode right pop.right;while (right!null){stack.add(right);rightright.left;}return pop.val;}public boolean hasNext() {return !stack.isEmpty();}}
/*** Your BSTIterator object will be instantiated and called as such:* BSTIterator obj new BSTIterator(root);* int param_1 obj.next();* boolean param_2 obj.hasNext();*/
