DAY10 - DFS

今天写广度优先搜寻(DFS)，与BFS相同，DFS是一种图形搜寻演算法，在解题的时候会用来爆搜的其中一种方法
直接上模板

模板&解释

尽可能探索每一个分支，走到底後回溯
模板像这样

void dfs(){
    if(越界或不合理状态)
        return
    for(对当前节点扩展){
        if(next_node合理&&未被访问){
            vis[next_node] = 1
            dfs(next_node)
            vis[next_node] = 0
        }
    }
}

例题实战

一样先上一题模板题，也是很经典的题目!!
46. 全排列

class Solution {
    vector<vector<int>> res;
public:
    vector<vector<int>> permute(vector<int>& nums) {
        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++){
            swap(nums[n], nums[i]);
            generate(nums, n+1);
            swap(nums[n], nums[i]);
        }
    }
};

100. 相同的树
这题可以用BFS与DFS写，可以比较这两天写的东西~~
((今天在讲dfs，就放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 {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {        
        if(p==nullptr&&q==nullptr){
            return true;
        }
        if(p==nullptr^q==nullptr){
            return false;
        }
        if(p->val==q->val){
            return isSameTree(p->left, q->left)&&isSameTree(p->right, q->right);
        }
        else{
            return false;
        }
    }
};