昨天写了DFS模板,今天就搭配模板放几题DFS的例题!!
void dfs(){
if(越界或不合理状态)
return
for(对当前节点扩展){
if(next_node合理&&未被访问){
vis[next_node] = 1
dfs(next_node)
vis[next_node] = 0
}
}
}
230. 二叉搜索树中第K小的元素
二元树&DFS
从程序码就会发现其实在应用的时候程序还是跟模板很像的,只要确认好调用的时机就好~~
/**
* 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 {
stack<int> sta;
public:
int kthSmallest(TreeNode* root, int k) {
dfs(root, k);
return sta.top();
}
void dfs(TreeNode* root, int k){
if(root==nullptr){
return;
}
dfs(root->left, k);
if(sta.size()==k){
return;
}
sta.push(root->val);
dfs(root->right, k);
}
};
剑指 Offer 36. 二叉搜索树与双向链表
这题是二元树的中序遍历
((其实就是一边中序遍历,一边指向正确的节点))
/*
// Definition for a Node.
class Node {
public:
int val;
Node* left;
Node* right;
Node() {}
Node(int _val) {
val = _val;
left = NULL;
right = NULL;
}
Node(int _val, Node* _left, Node* _right) {
val = _val;
left = _left;
right = _right;
}
};
*/
class Solution {
Node* front = nullptr;
Node* head = nullptr;
public:
/*二元树的中序遍历符合双向链的顺序*/
Node* treeToDoublyList(Node* root) {
if(root==nullptr){
return nullptr;
}
dfs(root);
front->right = head;
head->left = front;
return head;
}
void dfs(Node* curr){
if(curr==nullptr){
return;
}
dfs(curr->left);
if(front==nullptr){ //遍历到第一个节点
head = curr;
}
else{
front->right = curr;
}
curr->left = front;
front = curr;
dfs(curr->right);
}
};
47. 全排列 II
排列在昨天的文章有写了一题,这边再补一题允许重复的~~
class Solution {
vector<vector<int>> res;
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(), nums.end());
generate(nums, 0);
return res;
}
void generate(vector<int> nums, int n){
if(n >= nums.size())
{
res.push_back(nums);
return;
}
for(int i = n; i < nums.size(); i++)
{
if( i != n && nums[n] == nums[i])
continue;
swap(nums[n], nums[i]);
generate(nums, n+1);
}
return;
}
};
>>: [前端暴龙机,Vue2.x 进化 Vue3 ] Day2.在认识vue之前(二)
在Web 开发中,MVC 与三层架构这两个名词会经常被人提及,很多人会将它们混为一谈,认为MVC 就...
今天练了一下二维阵列 利用scanf将输入的数值与自己相乘後,并将结果反着印出,最後一个输入的数值第...
正文 前面几个章节有提到Service type LoadBalancer,这个service ty...
D9: while跟 do-while的差别 我原本一直以为do-while是要判断式成立时才会执行...
这篇将会综合前面的 GPIO 与 IIO 的知识,帮一个常见的红外线感测器 -- TCRC5000 ...