当前位置:网站首页>Leetcode problem solving -- 173 Binary search tree iterator
Leetcode problem solving -- 173 Binary search tree iterator
2022-07-06 03:07:00 【Snowy solitary boat】
Iterative thinking
private TreeNode node;
private Stack<TreeNode> stack;
public BSTIterator(TreeNode root) {
this.node =root;
stack = new Stack<>();
}
public int next() {
while (node !=null){
stack.push(node);
node = node.left;
}
node = stack.pop();
int next = node.val;
node = node.right;
return next;
}
public boolean hasNext() {
return node !=null||!stack.isEmpty();
}
Ideas : The iterative scheme based on the middle order traversal is improved
Every call next Get the value of a node
At the same time, the judgment conditions of the original cycle are extracted to hasNext Method to go
Be careful :
This scheme is based on the understanding of the iterative method of middle order traversal , If a little partner doesn't know , And I want to know more about the explanation idea of middle order traversal iteration , Sure Click here to jump
Other options
In fact, you can recursively traverse the tree once , Put it in an array , Creating index variables can also achieve the above functions ,leetcode The official also has corresponding solutions , But I want to , In fact, iterators are originally what I can do as much as you want , If it is realized in this way , Small amount of data is OK , If it's big data , It will undoubtedly cause bad time loss , So I didn't write it out , Interested students can Click here Jump leetcode Official explanation
边栏推荐
- [kubernetes series] learn the exposed application of kubernetes service security
- MySQL advanced notes
- codeforces每日5题(均1700)-第六天
- Introduction to robotframework (II) app startup of appui automation
- [concept] Web basic concept cognition
- 不赚钱的科大讯飞,投资价值该怎么看?
- Reverse repackaging of wechat applet
- 如何精准识别主数据?
- 2.13 simulation summary
- 如何做好功能测试
猜你喜欢
随机推荐
Misc (eternal night), the preliminary competition of the innovation practice competition of the National College Students' information security competition
Apt installation ZABBIX
Detailed use of dbutils # yyds dry goods inventory #
Polymorphic day02
NR modulation 1
Pat 1046 shortest distance (20 points) simulation
Résumé des méthodes de reconnaissance des caractères ocr
OCR文字识别方法综述
Pure QT version of Chinese chess: realize two-man, man-machine and network games
Data and Introspection__ dict__ Attributes and__ slots__ attribute
How to accurately identify master data?
MySQL advanced notes
Pat 1084 broken keyboard (20 points) string find
[unity3d] GUI control
OCR文字識別方法綜述
[matlab] access of variables and files
js 正则过滤和增加富文本中图片前缀
[kubernetes series] learn the exposed application of kubernetes service security
NR modulation 1
How to read excel, PDF and JSON files in R language?