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; }
略
