昨天寫了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;
}
};