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每日一练 专栏