C/C++每日一练(20230410) 二叉树专场(4)
目录
1. 二叉搜索树迭代器 🌟🌟🌟
2. 验证二叉搜索树 🌟🌟🌟
3. 不同的二叉搜索树 II 🌟🌟🌟
🌟 每日一练刷题专栏 🌟
Golang每日一练 专栏
Python每日一练 专栏
C/C++每日一练 专栏
Java每日一练 专栏
1. 二叉搜索树迭代器
实现一个二叉搜索树迭代器类BSTIterator
,表示一个按中序遍历二叉搜索树(BST)的迭代器:
BSTIterator(TreeNode root)
初始化BSTIterator
类的一个对象。BST 的根节点root
会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字,且该数字小于 BST 中的任何元素。boolean hasNext()
如果向指针右侧遍历存在数字,则返回true
;否则返回false
。int next()
将指针向右移动,然后返回指针处的数字。
注意,指针初始化为一个不存在于 BST 中的数字,所以对 next()
的首次调用将返回 BST 中的最小元素。
你可以假设 next()
调用总是有效的,也就是说,当调用 next()
时,BST 的中序遍历中至少存在一个下一个数字。
示例:
输入 ["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"] [[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []] 输出 [null, 3, 7, true, 9, true, 15, true, 20, false] 解释 BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]); bSTIterator.next(); // 返回 3 bSTIterator.next(); // 返回 7 bSTIterator.hasNext(); // 返回 True bSTIterator.next(); // 返回 9 bSTIterator.hasNext(); // 返回 True bSTIterator.next(); // 返回 15 bSTIterator.hasNext(); // 返回 True bSTIterator.next(); // 返回 20 bSTIterator.hasNext(); // 返回 False
提示:
- 树中节点的数目在范围
[1, 10^5]
内 0 <= Node.val <= 10^6
- 最多调用
10^5
次hasNext
和next
操作
进阶:
- 你可以设计一个满足下述条件的解决方案吗?
next()
和hasNext()
操作均摊时间复杂度为O(1)
,并使用O(h)
内存。其中h
是树的高度。
出处:
https://edu.csdn.net/practice/24633337
代码:
#define null INT_MIN
#include <bits/stdc++.h>
using namespace std;struct TreeNode
{int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};class BSTIterator
{
public:BSTIterator(TreeNode *root){for (; root != nullptr; root = root->left){sti_.push(root);}}/** @return the next smallest number */int next(){TreeNode *smallest = sti_.top();sti_.pop();int val = smallest->val;smallest = smallest->right;for (; smallest != nullptr; smallest = smallest->left){sti_.push(smallest);}return val;}/** @return whether we have a next smallest number */bool hasNext(){return !sti_.empty();}
private:stack<TreeNode *> sti_;
};
/*** 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();*/TreeNode* buildTree(vector<int>& nums)
{if (nums.empty()) return nullptr;TreeNode *root = new TreeNode(nums.front());queue<TreeNode*> q;q.push(root);int i = 1;while(!q.empty() && i < nums.size()){TreeNode *cur = q.front();q.pop();if(i < nums.size() && nums[i] != null){cur->left = new TreeNode(nums[i]);q.push(cur->left);}i++;if(i < nums.size() && nums[i] != null){cur->right = new TreeNode(nums[i]);q.push(cur->right);}i++;}return root;
}int main()
{vector<int> nums = {7, 3, 15, null, null, 9, 20};TreeNode *root = buildTree(nums);BSTIterator bSTIterator = BSTIterator(root); cout << bSTIterator.next() << endl; // 返回 3 cout << bSTIterator.next() << endl; // 返回 7 cout << (bSTIterator.hasNext() ? "True" : "False") << endl; // 返回 True cout << bSTIterator.next() << endl; // 返回 9 cout << (bSTIterator.hasNext() ? "True" : "False") << endl; // 返回 True cout << bSTIterator.next() << endl; // 返回 15 cout << (bSTIterator.hasNext() ? "True" : "False") << endl; // 返回 True cout << bSTIterator.next() << endl; // 返回 20 cout << (bSTIterator.hasNext() ? "True" : "False") << endl; // 返回 True return 0;
}
输出:
3
7
True
9
True
15
True
20
False
2. 验证二叉搜索树
给你一个二叉树的根节点 root
,判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下:
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:root = [2,1,3] 输出:true
示例 2:
输入:root = [5,1,4,null,null,3,6] 输出:false 解释:根节点的值是 5 ,但是右子节点的值是 4 。
提示:
- 树中节点数目范围在
[1, 10^4]
内 -2^31 <= Node.val <= 2^31 - 1
以下程序实现了这一功能,请你填补空白处内容:
```c++
#include <bits/stdc++.h>
using namespace std;
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 Solution
{
public:
bool isValidBST(TreeNode *root)
{
stack<TreeNode *> stk;
int prev = INT_MIN;
bool first = true;
while (!stk.empty() || root != nullptr)
{
if (root != nullptr)
{
stk.push(root);
root = root->left;
}
else
{
root = stk.top();
stk.pop();
_______________________;
}
}
return true;
}
};
```
出处:
https://edu.csdn.net/practice/25116236
代码:
#define null INT_MIN
#include <bits/stdc++.h>
using namespace std;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 Solution
{
public:bool isValidBST(TreeNode *root){stack<TreeNode *> stk;int prev = INT_MIN;bool first = true;while (!stk.empty() || root != nullptr){if (root != nullptr){stk.push(root);root = root->left;}else{root = stk.top();stk.pop();if (!first && prev >= root->val){return false;}first = false;prev = root->val;root = root->right;}}return true;}
};TreeNode* buildTree(vector<int>& nums)
{if (nums.empty()) return nullptr;TreeNode *root = new TreeNode(nums.front());queue<TreeNode*> q;q.push(root);int i = 1;while(!q.empty() && i < nums.size()){TreeNode *cur = q.front();q.pop();if(i < nums.size() && nums[i] != null){cur->left = new TreeNode(nums[i]);q.push(cur->left);}i++;if(i < nums.size() && nums[i] != null){cur->right = new TreeNode(nums[i]);q.push(cur->right);}i++;}return root;
}int main()
{Solution s;vector<int> nums = {2,1,3};TreeNode* root = buildTree(nums);cout << (s.isValidBST(root) ? "true" : "false") << endl;nums = {5,1,4,null,null,3,6};root = buildTree(nums);cout << (s.isValidBST(root) ? "true" : "false") << endl;return 0;
}
输出:
true
false
3. 不同的二叉搜索树 II
给你一个整数 n
,请你生成并返回所有由 n
个节点组成且节点值从 1
到 n
互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。
示例 1:
输入:n = 3 输出:[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
示例 2:
输入:n = 1 输出:[[1]]
提示:
1 <= n <= 8
代码:
#include <stdio.h>
#include <stdlib.h>struct TreeNode
{int val;struct TreeNode *left;struct TreeNode *right;
};static struct TreeNode *dfs(int low, int high, int *count)
{int i, j, k;if (low > high){*count = 0;return NULL;}else if (low == high){struct TreeNode *node = malloc(sizeof(*node));node->val = low;node->left = NULL;node->right = NULL;*count = 1;return node;}else{*count = 0;int capacity = 5;struct TreeNode *roots = malloc(capacity * sizeof(struct TreeNode));for (i = low; i <= high; i++){int left_cnt, right_cnt;struct TreeNode *left_subs = dfs(low, i - 1, &left_cnt);struct TreeNode *right_subs = dfs(i + 1, high, &right_cnt);if (left_cnt == 0)left_cnt = 1;if (right_cnt == 0)right_cnt = 1;if (*count + (left_cnt * right_cnt) >= capacity){capacity *= 2;capacity += left_cnt * right_cnt;roots = realloc(roots, capacity * sizeof(struct TreeNode));}for (j = 0; j < left_cnt; j++){for (k = 0; k < right_cnt; k++){roots[*count].val = i;roots[*count].left = left_subs == NULL ? NULL : &left_subs[j];roots[*count].right = right_subs == NULL ? NULL : &right_subs[k];(*count)++;}}}return roots;}
}static struct TreeNode **generateTrees(int n, int *returnSize)
{int i, count = 0;struct TreeNode *roots = dfs(1, n, &count);struct TreeNode **results = malloc(count * sizeof(struct TreeNode *));for (i = 0; i < count; i++){results[i] = &roots[i];}*returnSize = count;return results;
}static void dump(struct TreeNode *node)
{printf("%d ", node->val);if (node->left != NULL){dump(node->left);}else{printf("# ");}if (node->right != NULL){dump(node->right);}else{printf("# ");}
}int main(int argc, char **argv)
{if (argc != 2){fprintf(stderr, "Usage: ./test n\\n");exit(-1);}int i, count = 0;struct TreeNode **results = generateTrees(atoi(argv[1]), &count);for (i = 0; i < count; i++){dump(results[i]);printf("\\n");}return 0;
}
略
🌟 每日一练刷题专栏 🌟
✨ 持续,努力奋斗做强刷题搬运工!
👍 点赞,你的认可是我坚持的动力!
🌟 收藏,你的青睐是我努力的方向!
✎ 评论,你的意见是我进步的财富!
☸ 主页:https://hannyang.blog.csdn.net/
Golang每日一练 专栏 |
|
Python每日一练 专栏 |
|
C/C++每日一练 专栏 |
|
Java每日一练 专栏 |