LeetCode 173. Binary Search Tree Iterator(搜索二叉树)

题目

题意:实现一个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();   */