LeetCode 173. Binary Search Tree Iterator（搜索二叉树）
- 2020 年 2 月 14 日
- 笔记
题意：实现一个BST的Next（）函数，输出BST里的从小到大的数字。
题解：题目说Next()的时间效率O(1),空间效率O(h),h为树的高度。我们维护一个栈，把前序遍历的左子树的结果存进去。
每次Next取出栈顶元素的时候，再遍历栈顶元素的右子树的前序遍历的左子树部分。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class BSTIterator { public: vector<TreeNode*> stack; BSTIterator(TreeNode* root) { if(root!=NULL) DFS(root); } /** @return the next smallest number */ int next() { TreeNode* term = stack[stack.size()-1]; stack.pop_back(); if(term->right!=NULL) { DFS(term->right); } return term->val; } /** @return whether we have a next smallest number */ bool hasNext() { if(stack.size()!=0) return true; else return false; } void DFS(TreeNode* term) { stack.push_back(term); if(term->left!=NULL) DFS(term->left); } }; /** * Your BSTIterator object will be instantiated and called as such: * BSTIterator* obj = new BSTIterator(root); * int param_1 = obj->next(); * bool param_2 = obj->hasNext(); */
