递归，回溯，DFS，BFS的理解和模板

LeetCode 里面很大一部分题目都是属于这个范围，例如Path Sum用的就是递归+DFS，Path Sum2用的是递归+DFS+回溯

这里参考了一些网上写得很不错的文章，总结一下理解与模板

递归：就是出现这种情况的代码： （或者说是用到了栈）

解答树角度：在dfs遍历一棵解答树

优点：结构简洁

缺点：效率低，可能栈溢出

递归的一般结构：

将（起始）首节点加入队列： q.push(head);                     标记首节点已经被访问：         isvisited[head]=true;                    以下自动反应：                       while(!q.empty())                                                                    {                                                                          int temp=q.front();                                                                           q.pop();                                                                          访问temp，并标记temp已被访问过，将temp的子相关节点加入队列                                                                          q.push(temp相关节点);                                                                    }

格式：将所有节点遍历一遍，在遍历每个节点是，DFS的遍历该节点相关的所有节点

void dfs(int x, int y){if(!mat[x][y] || vis[x][y]) return;     // 曾经访问过这个格子，或者当前格子是白色vis[x][y] = 1;                          // 标记(x,y)已访问过dfs(x-1,y-1); dfs(x-1,y); dfs(x-1,y+1);dfs(x-1,y);               dfs(x,y+1);dfs(x+1,y-1); dfs(x+1,y); dfs(x+1,y+1); // 递归访问周围的八个格子}主循环：for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)if(!vis[i][j] && mat[i][j]){count++;dfs(i,j);} // 找到没有访问过的黑格

http://hi.baidu.com/silverxinger/item/cdcd900ca34e988402ce1ba0

http://hi.baidu.com/lvhuyh/item/960c5b163c4d7cd539cb309b

http://www.cnblogs.com/HectorInsanE/archive/2010/11/09/1872656.html