首页 > 代码库 > 【leetcode】Binary Search Tree Iterator
【leetcode】Binary Search Tree Iterator
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.
最简单的，先把整棵树给遍历了，找到所有的值
1 /** 2 * Definition for binary tree 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */10 class BSTIterator {11 public:12 13 vector<int> vals;14 int index;15 BSTIterator(TreeNode *root) {16 DFS(root);17 index=-1;18 }19 20 void DFS(TreeNode *root)21 {22 23 if(root==NULL) return;24 25 DFS(root->left);26 vals.push_back(root->val);27 DFS(root->right);28 }29 30 /** @return whether we have a next smallest number */31 bool hasNext() {32 33 if(index<(int)vals.size()-1) return true;34 else return false;35 36 }37 38 /** @return the next smallest number */39 int next() {40 return vals[++index];41 }42 };43 44 /**45 * Your BSTIterator will be called like this:46 * BSTIterator i = BSTIterator(root);47 * while (i.hasNext()) cout << i.next();48 */
运用二叉排序树的性质
首先连同root把所有左边节点都push到堆栈中，
然后每当调用next时，返回堆栈栈顶元素，然后把栈顶元素的右孩子，以及他的所有左子树都压入栈即可
1 /** 2 * Definition for binary tree 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */10 class BSTIterator {11 public:12 13 stack<TreeNode*> stk;14 BSTIterator(TreeNode *root) {15 pushLeftNode(root);16 17 }18 19 void pushLeftNode(TreeNode *root)20 {21 22 while(root!=NULL)23 {24 stk.push(root);25 root=root->left;26 }27 }28 29 30 31 /** @return whether we have a next smallest number */32 bool hasNext() {33 34 return !stk.empty();35 }36 37 /** @return the next smallest number */38 int next() {39 40 TreeNode * smallestNode=stk.top();41 stk.pop();42 pushLeftNode(smallestNode->right);43 return smallestNode->val;44 }45 };46 47 /**48 * Your BSTIterator will be called like this:49 * BSTIterator i = BSTIterator(root);50 * while (i.hasNext()) cout << i.next();51 */
【leetcode】Binary Search Tree Iterator
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。