代码拉取完成,页面将自动刷新
package com.hit.basmath.learn.binary_search_tree;
import com.hit.common.TreeNode;
import java.util.Stack;
/**
* 173. Binary Search Tree Iterator
* <p>
* Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.
* <p>
* Calling next() will return the next smallest number in the BST.
* <p>
* Example:
* <p>
* BSTIterator iterator = new BSTIterator(root);
* iterator.next(); // return 3
* iterator.next(); // return 7
* iterator.hasNext(); // return true
* iterator.next(); // return 9
* iterator.hasNext(); // return true
* iterator.next(); // return 15
* iterator.hasNext(); // return true
* iterator.next(); // return 20
* iterator.hasNext(); // return false
* <p>
* Note:
* <p>
* 1. next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.
* 2. You may assume that next() call will always be valid, that is, there will be at least a next smallest number in the BST when next() is called.
*/
public class _173 {
class BSTIterator {
private Stack<TreeNode> stack = new Stack<TreeNode>();
public BSTIterator(TreeNode root) {
pushAll(root);
}
/**
* @return whether we have a next smallest number
*/
public boolean hasNext() {
return !stack.isEmpty();
}
/**
* @return the next smallest number
*/
public int next() {
TreeNode tmpNode = stack.pop();
pushAll(tmpNode.right);
return tmpNode.val;
}
private void pushAll(TreeNode node) {
while (node != null) {
stack.push(node);
node = node.left;
}
}
}
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。