gpt4 book ai didi

C++实现LeetCode(173.二叉搜索树迭代器)

转载 作者:qq735679552 更新时间:2022-09-27 22:32:09 35 4
gpt4 key购买 nike

CFSDN坚持开源创造价值,我们致力于搭建一个资源共享平台,让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章C++实现LeetCode(173.二叉搜索树迭代器)由作者收集整理,如果你对这篇文章有兴趣,记得点赞哟.

[LeetCode] 173.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. 。

Credits: Special thanks to @ts for adding this problem and creating all test cases. 。

这道题主要就是考二叉树的中序遍历的非递归形式,需要额外定义一个栈来辅助,二叉搜索树的建树规则就是左<根<右,用中序遍历即可从小到大取出所有节点。代码如下:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
  * Definition for binary tree
  * struct TreeNode {
  *     int val;
  *     TreeNode *left;
  *     TreeNode *right;
  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  * };
  */
class BSTIterator {
public :
     BSTIterator(TreeNode *root) {
         while (root) {
             s.push(root);
             root = root->left;
         }
     }
 
     /** @return whether we have a next smallest number */
     bool hasNext() {
         return !s.empty();
     }
 
     /** @return the next smallest number */
     int next() {
         TreeNode *n = s.top();
         s.pop();
         int res = n->val;
         if (n->right) {
             n = n->right;
             while (n) {
                 s.push(n);
                 n = n->left;
             }
         }
         return res;
     }
private :
     stack<TreeNode*> s;
};
 
/**
  * Your BSTIterator will be called like this:
  * BSTIterator i = BSTIterator(root);
  * while (i.hasNext()) cout << i.next();
  */

原文链接:https://www.cnblogs.com/grandyang/p/4231455.html 。

最后此篇关于C++实现LeetCode(173.二叉搜索树迭代器)的文章就讲到这里了,如果你想了解更多关于C++实现LeetCode(173.二叉搜索树迭代器)的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。

35 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com