LeetCode 94. 二叉树的中序遍历
题目类型
- 中序遍历
题目链接
思路
AC代码
class Solution {
public:
vector<int> res;
void inorder(TreeNode* root)
{
if (!root) return;
inorder(root->left);
res.push_back(root->val);
inorder(root->right);
return;
}
vector<int> inorderTraversal(TreeNode* root) {
inorder(root);
return res;
}
};
LeetCode 95. 不同的二叉搜索树 II
题目类型
- DFS回溯
题目链接
思路
这道题不看题解的话 我想不出来 呜呜呜
- 写一个generate(int l, int r)函数，该函数枚举(l, r)的每一个点i，在(l, i - 1)上构造左子树集合，在(i + 1, r)上构造右子树集合
- 然后将左子树集合和右子树集合 与根节点拼接
AC代码
class Solution {
public:
vector<TreeNode*> dfs(int l, int r)
{
if (l > r) return {nullptr};
// 存放结果集合
vector<TreeNode*> res;
// 枚举根节点
for (int i = l; i <= r; i ++)
{
vector<TreeNode*> left = dfs(l, i - 1);
vector<TreeNode*> right = dfs(i + 1, r);
// 枚举左子树和右子树集合
// 拼接左子树和右子树
for (auto l : left)
{
for (auto r : right)
{
// 以i为根节点
TreeNode* root = new TreeNode(i);
root->left = l;
root->right = r;
res.push_back(root);
}
}
}
return res;
}
vector<TreeNode*> generateTrees(int n) {
if (n == 0) return {};
return dfs(1, n);
}
};
LeetCode 95. 不同的二叉搜索树
题目类型
- 卡兰特数
题目链接
思路
AC代码
class Solution {
public:
int numTrees(int n) {
long long c = 1;
for (int i = 0; i < n; i ++)
{
c = 2 * c * (2 * i + 1) / (i + 2);
}
return (int) c;
}
};
LeetCode 98. 验证二叉搜索树
题目类型
- 中序遍历
题目链接
https://leetcode.cn/problems/validate-binary-search-tree/submissions/
思路
此题是22年408统考的题，其实408统考题大部分在力扣都能找到
方法1：中序遍历
AC代码 （中序遍历）
class Solution {
public:
bool isValidBST(TreeNode* root) {
return dfs(root, LONG_MIN, LONG_MAX);
}
bool dfs(TreeNode* root, long long lower, long long upper)
{
if (root == nullptr) return true;
if (root->val <= lower || root->val >= upper) return false;
return ( dfs(root->left, lower, root->val) && dfs(root->right, root->val, upper));
}
};
LeetCode 99. 恢复二叉搜索树
题目类型
思路
AC代码
##
题目类型
思路
AC代码
##
题目类型
思路
AC代码
##
题目类型
思路
AC代码
LeetCode 102. 验证二叉搜索树
题目类型
- 层序遍历
题目链接
https://leetcode.cn/problems/binary-tree-level-order-traversal/
思路
简单的数据结构题，使用队列即可，不同点在于每一层分开输出，在开始访问每一层时，当前队列的长度为该结点个数，记录下来即可
AC代码
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> q;
vector<vector<int>> res;
if (!root) return res;
q.push(root);
while (q.size())
{
int currentLevelSize = q.size();
res.push_back(vector<int> ());
// 队列中元素个数为当前层的结点个数
for (int i = 0; i < currentLevelSize; i ++)
{
TreeNode* node = q.front(); q.pop();
res.back().push_back(node->val);
// 将node结点的左右孩子放入队列中
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return res;
}
};
##
题目类型
思路
AC代码
##
题目类型
思路
AC代码
##【未完待更】
