首页 > 代码库 > 【LeetCode】Binary Search Tree Iterator (2 solutions)
【LeetCode】Binary Search Tree Iterator (2 solutions)
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.
解法一：
中序遍历后装入队列，顺序输出。
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class BSTIterator {public: queue<int> minq; map<TreeNode*, bool> m; stack<TreeNode *> s; BSTIterator(TreeNode *root) { //inOrder traversal if(root != NULL) { s.push(root); m[root] = true; while(!s.empty()) { TreeNode* top = s.top(); if(top->left && m.find(top->left) == m.end()) { s.push(top->left); m[top->left] = true; continue; } minq.push(top->val); s.pop(); if(top->right && m.find(top->right) == m.end()) { s.push(top->right); m[top->right] = true; } } } } /** @return whether we have a next smallest number */ bool hasNext() { return !minq.empty(); } /** @return the next smallest number */ int next() { int front = minq.front(); minq.pop(); return front; }};/** * Your BSTIterator will be called like this: * BSTIterator i = BSTIterator(root); * while (i.hasNext()) cout << i.next(); */
解法二：
Thanks to xcv58，无需预先进行全部遍历。
利用中序遍历的递归思想：当子树的根节点访问完成后，后续节点为中序遍历该根节点右子树
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class BSTIterator {public: stack<TreeNode *> s; BSTIterator(TreeNode *root) { pushLeft(root); } /** @return whether we have a next smallest number */ bool hasNext() { return !s.empty(); } /** @return the next smallest number */ int next() { TreeNode* top = s.top(); s.pop(); pushLeft(top->right); return top->val; } void pushLeft(TreeNode* root) { if(root != NULL) { s.push(root); TreeNode* cur = root; while(cur->left) { s.push(cur->left); cur = cur->left; } } }};/** * Your BSTIterator will be called like this: * BSTIterator i = BSTIterator(root); * while (i.hasNext()) cout << i.next(); */
【LeetCode】Binary Search Tree Iterator (2 solutions)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。