子集
方法一：
??位运算，如果数组的长度为3，则枚举000到111，000表示空集，111表示集合本身。
代码：
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> res;
vector<int> temp;
int n = nums.size();
for(int i = 0; i < (1 << n); i++) {
temp.clear();
for(int j = 0; j < n; j++) {
if(i & (1 << j)) {
temp.push_back(nums[j]);
}
}
res.push_back(temp);
}
return res;
}
};
方法二：
??递归实现枚举，背模板。
代码：
class Solution {
public:
vector<int> t;
vector<vector<int>> ans;
void dfs(int cur, vector<int>& nums) {
if (cur == nums.size()) {
ans.push_back(t);
return;
}
t.push_back(nums[cur]); //选择下一个
dfs(cur + 1, nums);
t.pop_back(); //不选择下一个
dfs(cur + 1, nums);
}
vector<vector<int>> subsets(vector<int>& nums) {
dfs(0, nums);
return ans;
}
};
单词搜索
不同的二叉搜索树
分析：
??卡特兰数，详见：算法中的数学—卡特兰数（解析+代码实现）
代码：
class Solution {
public:
int numTrees(int n) {
vector<long long> dp(20);
dp[0] = dp[1] = 1;
for(int i = 2; i <= 19; i++) {
dp[i] = dp[i - 1] * (4 * i - 2) / (i + 1);
}
return dp[n];
}
};
验证二叉搜索树
方法一：
??二叉搜索树的中序遍历是一个递增序列。
代码：
/**
* Definition for a binary tree node.
* 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:
vector<int> res;
void dfs(TreeNode* root) {
if(root) {
dfs(root->left);
res.push_back(root->val);
dfs(root->right);
}
}
bool isValidBST(TreeNode* root) {
dfs(root);
for(int i = 0; i < res.size() - 1; i++) {
if(res[i] < res[i + 1]) {
continue;
}else {
return false;
}
}
return true;
}
};
方法二：
??参考官方题解：递归。
代码：
class Solution {
public:
bool helper(TreeNode* root, long long lower, long long upper) {
if (root == nullptr) {
return true;
}
if (root -> val <= lower || root -> val >= upper) {
return false;
}
return helper(root -> left, lower, root -> val) && helper(root -> right, root -> val, upper);
}
bool isValidBST(TreeNode* root) {
return helper(root, LONG_MIN, LONG_MAX);
}
};
二叉树的层序遍历
分析：
??二叉树的层序遍历，背模板。
代码：
/**
* Definition for a binary tree node.
* 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:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if(root == nullptr) {
return res;
}
queue<TreeNode*> que;
que.push(root);
vector<int> temp;
while(!que.empty()) {
int n = que.size();
temp.clear();
for(int i = 0; i < n; i++) {
TreeNode* t = que.front();
que.pop();
temp.push_back(t->val);
if(t->left) {
que.push(t->left);
}
if(t->right) {
que.push(t->right);
}
}
res.push_back(temp);
}
return res;
}
};
从前序与中序遍历序列构造二叉树
分析：
??递归构造二叉树。
代码：
/**
* Definition for a binary tree node.
* 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 {
private:
unordered_map<int, int> mp;
public:
TreeNode* create(vector<int>& pre, vector<int>& in, int x1, int x2, int x3, int x4) {
if(x1 > x2) {
return NULL;
}
int root_val = pre[x1];
//创建根
TreeNode* root = new TreeNode(root_val);
int x = mp[root_val]; //中序遍历中的位置
int y = x - x3 + x1;
int z = x2 - x4 + x + 1;
//创建左子树
root->left = create(pre, in, x1 + 1, y, x3, x - 1);
root->right = create(pre, in, z, x2, x + 1, x4);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int n = preorder.size();
// 构造哈希映射,快速定位根节点
for (int i = 0; i < n; ++i) {
mp[inorder[i]] = i;
}
return create(preorder, inorder, 0, n - 1, 0, n - 1);
}
};