Binary Search Tree Iterator (M)
題目
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.
Example:
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
Note:
next()andhasNext()should run in average O(1) time and uses O(h) memory, where h is the height of the tree.- You may assume that
next()call will always be valid, that is, there will be at least a next smallest number in the BST whennext()is called.
題意
實作一個BST迭代器，要求next()和hasNext()的平均時間復雜度為\(O(1)\)且空間復雜度為\(O(h)\)，
思路
如果沒有復雜度限制，那么最簡單的方法就是先一遍中序遍歷將所有值記錄下來，呼叫next()時挨個回傳就行，空間復雜度為\(O(h)\)，做法就參考中序遍歷的迭代實作：初始化時先將最左側的邊存盤下來，每次呼叫next()時，堆疊頂元素就是下一個應回傳的結點，出堆疊后將該結點右子樹的最左側邊存入堆疊，重復上述程序，堆疊中元素數量最大為樹高，且查詢平均復雜度為\(O(1)\)，
代碼實作
Java
class BSTIterator {
private Deque<TreeNode> stack;
private int index;
public BSTIterator(TreeNode root) {
stack = new ArrayDeque<>();
while (root != null) {
stack.push(root);
root = root.left;
}
}
/**
* @return the next smallest number
*/
public int next() {
TreeNode node = stack.pop();
TreeNode tmp = node.right;
while (tmp != null) {
stack.push(tmp);
tmp = tmp.left;
}
return node.val;
}
/**
* @return whether we have a next smallest number
*/
public boolean hasNext() {
return !stack.isEmpty();
}
}
JavaScript
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
*/
var BSTIterator = function (root) {
this.stack = []
while (root) {
this.stack.push(root)
root = root.left
}
}
/**
* @return {number}
*/
BSTIterator.prototype.next = function () {
let top = this.stack.pop()
let p = top.right
while (p) {
this.stack.push(p)
p = p.left
}
return top.val
}
/**
* @return {boolean}
*/
BSTIterator.prototype.hasNext = function () {
return this.stack.length
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/232367.html
標籤：其他
上一篇：MySQL問題記錄——2003-Can't connect to MySQL server on 'localhost'(10038)