LeetCode Binary Search Tree Iterator
2024-10-08 13:47:39
原题链接在这里:https://leetcode.com/problems/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.
题解:
用一个stack把所有最左边的node压进 stack中。
判断hasNext()时就是看stack 是否为空.
next()返回stack顶部top元素,若是top有右子树,就把右子树的所有最左node压入stack中.
constructor time complexity: O(h).
hashNext time complexity: O(1).
next time complexity: O(h).
Space: O(h), stack 最大为树的高度。
AC Java:
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/ public class BSTIterator {
Stack<TreeNode> stk; public BSTIterator(TreeNode root) {
stk = new Stack<TreeNode>();
while(root != null){
stk.push(root);
root = root.left;
}
} /** @return whether we have a next smallest number */
public boolean hasNext() {
return !stk.isEmpty();
} /** @return the next smallest number */
public int next() {
TreeNode top = stk.pop();
TreeNode rightLeft = top.right;
while(rightLeft != null){
stk.push(rightLeft);
rightLeft = rightLeft.left;
} return top.val;
}
} /**
* Your BSTIterator will be called like this:
* BSTIterator i = new BSTIterator(root);
* while (i.hasNext()) v[f()] = i.next();
*/
类似Binary Tree Inorder Traversal, Inorder Successor in BST.
最新文章
- android 编译过程
- ResourceManager没启动
- BZOJ4517——[Sdoi2016]排列计数
- Cocos2d-x3.x塔防游戏(保卫萝卜)从零开始(三)
- USACO 3.2 kimbits DP
- go语言实现的目录共享程序
- -_-#【减少 DOM 访问】“离线”更新节点,再将它们添加到树中
- NOI十连测 第六测 T1
- 解决open-vm-tools安装时Failed to get unit file state for run-vmblockx2dfuse.mount
- jQuery遍历函数
- AsyncHandler
- [译][待续]Chap1.Using neural nets to recognize handwritten digits
- touchmover手机移动端的拖动
- 使用VS Code开发asp.net core (下)
- Java中使用long类型实现精确的四则运算
- 教程一 openwrt路由器入门 远程命令行+文件系统
- Oracle merge合并更新函数
- ngx-moment汉化
- 微信小程序自定义组件
- mysql update ...select的使用 &; update 遇到 disable safe 的解决方法