【LeetCode】173. Binary Search Tree Iterator (2 solutions)
LeetCode Tree search Binary Iterator Solutions
2023-09-11 14:20:27 时间
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.
Credits:
Special thanks to @ts for adding this problem and creating all test cases.
解法一:暴力解法先不考虑空间复杂度
中序遍历后装入队列,顺序输出。
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class BSTIterator { public: queue<int> minq; map<TreeNode*, bool> m; stack<TreeNode *> s; BSTIterator(TreeNode *root) { //inOrder traversal if(root != NULL) { s.push(root); m[root] = true; while(!s.empty()) { TreeNode* top = s.top(); if(top->left && m.find(top->left) == m.end()) { s.push(top->left); m[top->left] = true; continue; } minq.push(top->val); s.pop(); if(top->right && m.find(top->right) == m.end()) { s.push(top->right); m[top->right] = true; } } } } /** @return whether we have a next smallest number */ bool hasNext() { return !minq.empty(); } /** @return the next smallest number */ int next() { int front = minq.front(); minq.pop(); return front; } }; /** * Your BSTIterator will be called like this: * BSTIterator i = BSTIterator(root); * while (i.hasNext()) cout << i.next(); */
解法二:空间复杂度O(h)的解法
每次取出栈顶元素(即当前最小)后,查找下一个元素并压栈。
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class BSTIterator { public: stack<TreeNode*> stk; int nextmin; BSTIterator(TreeNode *root) { while(root) { stk.push(root); root = root->left; } } /** @return whether we have a next smallest number */ bool hasNext() { if(!stk.empty()) { TreeNode* top = stk.top(); stk.pop(); nextmin = top->val; TreeNode* cur = top->right; if(cur) { stk.push(cur); cur = cur->left; while(cur) { stk.push(cur); cur = cur->left; } } return true; } else return false; } /** @return the next smallest number */ int next() { return nextmin; } }; /** * Your BSTIterator will be called like this: * BSTIterator i = BSTIterator(root); * while (i.hasNext()) cout << i.next(); */
相关文章
- Leetcode: Subtree of Another Tree
- Leetcode: Range Sum Query - Mutable && Summary: Segment Tree
- Leetcode: Closest Binary Search Tree Value
- Leetcode: Validate Binary Search Tree
- leetcode第一刷_Convert Sorted Array to Binary Search Tree
- Binary Search Tree 以及一道 LeetCode 题目
- JS Leetcode 154. 寻找旋转排序数组中的最小值 II 题解分析
- [LeetCode] Linked List Cycle II
- [LeetCode] Binary Tree Zigzag Level Order Traversal
- [LeetCode] Construct Binary Tree from Preorder and Inorder Traversal
- [LeetCode] Flatten Binary Tree to Linked List
- 【LeetCode】235. Lowest Common Ancestor of a Binary Search Tree (2 solutions)
- 【LeetCode】98. Validate Binary Search Tree (2 solutions)
- 【LeetCode】108. Convert Sorted Array to Binary Search Tree
- [LeetCode] Convert Sorted Array to Binary Search Tree
- [LeetCode-20]Construct Binary Tree from Inorder and Postorder Traversal
- LeetCode——Convert Sorted Array to Binary Search Tree
- [LeetCode] 1038. Binary Search Tree to Greater Sum Tree 二叉搜索树到较大和树
- [LeetCode] 1008. Construct Binary Search Tree from Preorder Traversal 从先序遍历重建二叉搜索树
- [LeetCode] 987. Vertical Order Traversal of a Binary Tree 竖直遍历二叉树
- [LeetCode] 834. Sum of Distances in Tree 树中距离之和
- [LeetCode] 365. Water and Jug Problem 水罐问题
- [LeetCode] 272. Closest Binary Search Tree Value II 最近的二分搜索树的值之二
- [LeetCode] 235. Lowest Common Ancestor of a Binary Search Tree 二叉搜索树的最小共同父节点
- [LeetCode] 106. Construct Binary Tree from Inorder and Postorder Traversal 由中序和后序遍历建立二叉树
- [LeetCode] Binary Search Tree Iterator 二叉搜索树迭代器
- leetcode 145. Binary Tree Postorder Traversal 二叉树的后序遍历 (中等)
- leetcode 889. Construct Binary Tree from Preorder and Postorder Traversal 根据前序和后