贵阳市做网站电话,app开发公司怎么查看,新建网站如何推广,seo分析是什么意思Every day a Leetcode
题目来源#xff1a;173. 二叉搜索树迭代器
解法1#xff1a;中序遍历
我们可以直接对二叉搜索树做一次完全的递归遍历#xff0c;获取中序遍历的全部结果并保存在数组中。随后#xff0c;我们利用得到的数组本身来实现迭代器。
代码#xff1a…Every day a Leetcode
题目来源173. 二叉搜索树迭代器
解法1中序遍历
我们可以直接对二叉搜索树做一次完全的递归遍历获取中序遍历的全部结果并保存在数组中。随后我们利用得到的数组本身来实现迭代器。
代码
/** lc appleetcode.cn id173 langcpp** [173] 二叉搜索树迭代器*/// lc codestart
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class BSTIterator
{
private:int index 0;vectorint nums;// 辅函数void inOrder(TreeNode *root, vectorint nums){if (root nullptr)return;inOrder(root-left, nums);nums.push_back(root-val);inOrder(root-right, nums);}// 中序遍历vectorint inOrderTraversal(TreeNode *root){vectorint res;inOrder(root, res);return res;}public:BSTIterator(TreeNode *root) : index(0), nums(inOrderTraversal(root)){}int next(){int num nums[index];index;return num;}bool hasNext(){return (index nums.size());}
};/*** 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();*/
// lc codeend结果 复杂度分析
时间复杂度初始化需要 O(n) 的时间其中 n 为树中节点的数量。随后每次调用只需要 O(1) 的时间。
空间复杂度O(n)因为需要保存中序遍历的全部结果。
解法2迭代
除了递归的方法外我们还可以利用栈这一数据结构通过迭代的方式对二叉树做中序遍历。此时我们无需预先计算出中序遍历的全部结果只需要实时维护当前栈的情况即可。
代码
class BSTIterator {
private:TreeNode* cur;stackTreeNode* stk;
public:BSTIterator(TreeNode* root): cur(root) {}int next() {while (cur ! nullptr) {stk.push(cur);cur cur-left;}cur stk.top();stk.pop();int ret cur-val;cur cur-right;return ret;}bool hasNext() {return cur ! nullptr || !stk.empty();}
};结果 复杂度分析
