DFS专项练习

DFS专题

leetcode 104. 二叉树的最大深度

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
#include<algorithm>
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root==NULL)return 0;
        int l1=maxDepth(root->left);
        int l2=maxDepth(root->right);
        return max(l1,l2)+1;
    }

DFS模板总结

void dfs()//参数用来表示状态  {  
    if(到达终点状态)  {  
        ...//根据题意添加  
        return;  
    }  
    if(越界或者是不合法状态)  
        return;  
    if(特殊状态)//剪枝
        return ;
    for(扩展方式)  {  
        if(扩展方式所达到状态合法)  
        {  
            修改操作;//根据题意来添加  
            标记；  
            dfs（）；  
            (还原标记)；  // visited[i] = 1;
            //是否还原标记根据题意  
            //如果加上（还原标记）就是 回溯法  
            // visited[i] = 0
        }  
 
    }  
}

全排列问题

#include<iostream>
#include<cmath>
using namespace std;
 
int p[10]={0};
bool vis[10]={0};
int n;
void dfs(int x){
	if (x==n+1){
		for(int i=1;i<=n;i++)
		cout<<p[i]<<" ";
		cout<<endl;
		return ;
	}
	
	for (int i=1;i<=n;i++){
		if (vis[i]==false  )
		{
			p[x] = i;
			vis[i] = true;
			
			dfs(x+1);
			vis[i] = false;
		}
	}
}
 
int main(){
	n=4;
	dfs(1);
	return 0;
}