[leetcode] 173. Binary Search Tree Iterator

[leetcode] 173. Binary Search Tree Iterator

Description

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 3iterator.next(); // return 7iterator.hasNext(); // return trueiterator.next(); // return 9iterator.hasNext(); // return trueiterator.next(); // return 15iterator.hasNext(); // return trueiterator.next(); // return 20iterator.hasNext(); // return false

Note:

next() and hasNext() 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 when next() is called.

分析

题目的意思是： 实现一个二叉搜索树的遍历迭代器，其中要有next(),hasNext()函数，要求时间复杂度为O(1), 空间复杂度为O(h),h为树的高度。

-这道题我不会，结果看别人的解析，用一个栈就能解决，我要哭了。 初始化的时候，把二叉树遍历root->left压入栈中， next函数的实现： 把栈顶的元素输出，如果出栈的元素有右分支，把t->right,遍历t->left押入栈中。 hasNext()： 判断一下节点是否为空就行了。

如果读者还是不理解，就直接看代码手动模拟吧，栈能够保证遍历按照从小到大输出。

代码

/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class BSTIterator {private: stack s;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* t=s-(); s.pop(); int res=t->val; if(t->right){ t=t->right; while(t){ s.push(t); t=t->left; } } return res; }};/** * Your BSTIterator will be called like this: * BSTIterator i = BSTIterator(root); * while (i.hasNext()) cout << i.next(); */

参考文献

​​[LeetCode] Binary Search Tree Iterator 二叉搜索树迭代器​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。