[LeetCode]173.Binary Search Tree Iterator

本文主要是介绍[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.

【分析】

中序遍历

【代码】

/*********************************
*   日期：2015-01-03
*   作者：SJF0115
*   题目: 173.Binary Search Tree Iterator
*   来源：https://oj.leetcode.com/problems/binary-search-tree-iterator/
*   结果：AC
*   来源：LeetCode
*   博客：
**********************************/
#include <iostream>
#include <stack>
#include <vector>
using namespace std;// 二叉查找树节点
struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 插入
void TreeInsert(TreeNode*& root,int val){// 创建新节点TreeNode* node = new TreeNode(val);// 空树if(root == NULL){root = node;return;}//ifTreeNode *pre = NULL;TreeNode *p = root;// 寻找插入位置while(p){// 父节点pre = p;// 沿左子树方向下降if(val < p->val){p = p->left;}//if// 沿右子树方向下降else{p = p->right;}//else}//while// 左子结点处插入if(val < pre->val){pre->left = node;}//if// 右子结点处插入else{pre->right = node;}//else
}
// 创建二叉查找树
TreeNode* TreeCreate(vector<int> num){TreeNode *root = NULL;int len = num.size();if(len == 0){return root;}//iffor(int i = 0;i < len;i++){TreeInsert(root,num[i]);}//forreturn root;
}
class BSTIterator {
public:BSTIterator(TreeNode *root) {TreeNode *p = root;// 沿左子树下降while(p){s.push(p);p = p->left;}//while}/** @return whether we have a next smallest number */bool hasNext() {if(!s.empty()){return true;}//ifreturn false;}/** @return the next smallest number */int next() {TreeNode *p = NULL;// 出栈p = s.top();s.pop();int val = p->val;// 转向右子树if(p->right){p = p->right;// 沿左子树下降while(p){s.push(p);p = p->left;}//while}//ifreturn val;}
private:stack<TreeNode*> s;
};int main() {// -1代表NULLvector<int> num = {8,3,1,10,6,14,4,7,13};TreeNode *root = TreeCreate(num);BSTIterator bSTIterator = BSTIterator(root);while(bSTIterator.hasNext()){cout<<bSTIterator.next()<<endl;}
}

【代码二】

class BSTIterator {stack<TreeNode *> myStack;
public:BSTIterator(TreeNode *root) {pushAll(root);}/** @return whether we have a next smallest number */bool hasNext() {return !myStack.empty();}/** @return the next smallest number */int next() {TreeNode *tmpNode = myStack.top();myStack.pop();pushAll(tmpNode->right);return tmpNode->val;}private:void pushAll(TreeNode *node) {for (; node != NULL; myStack.push(node), node = node->left);}
};

这篇关于[LeetCode]173.Binary Search Tree Iterator的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---