今天寫廣度優先搜尋(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;
        }
    }
};