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(); */
