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/文章来源地址https://www.toymoban.com/news/detail-411359.html

	Golang每日一练 专栏
	Python每日一练 专栏
	C/C++每日一练 专栏
	Java每日一练 专栏

到了这里，关于C/C++每日一练(20230410) 二叉树专场（4）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！