注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex173 Binary Search Tree Iterator  

2015-05-19 23:05:50|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
这一题想复杂了,以为和minstack是一样,而且后来想的方法是做一条链表,然后从小到大排序。其实这个链表就是平衡树的中序遍历的过程。

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.

直接构造一个队列,中序遍历过程存到里面就行了。见c代码

/*
* 也可以写一个c语言实现的队列,懒得写了
*/
class BSTIterator {
queue<TreeNode*> bst;
public:
BSTIterator(TreeNode *root) {
inOrder(root);

}

/** @return whether we have a next smallest number */
bool hasNext() {
if (bst.empty())
return false;
return true;
}

/** @return the next smallest number */
int next() {
TreeNode *current = bst.front();
bst.pop();
return current->val;
}
void inOrder(TreeNode *root)
{
if (root != NULL)
{
inOrder(root->left);
bst.push(root);
inOrder(root->right);
}
}
};



ps:吐槽一下,后面的题貌似好多都是关于string处理的问题,都不给c语言的选项了,看来还是要用c++来写代码了。
今天做了6题,严格来说是7题,把ex95用c代码写了一遍,我也是够搞笑的~~
  评论这张
 
阅读(17)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017