图的遍历bfs dfs模板及其解决二叉树层次遍历_dfs算法适合求解二叉树层序遍历,图遍历,最短路径,组合问题

1 bfs

  广度优先搜索（bfs） 和深度优先搜索都是的图的经典搜索算法之一，我们这里先给出一些模板。简单理解就是树的层次遍历，对于图的时候，也是按层，具体的就是节点与根节点的距离进行分层。通常是使用队列进行维护。有一些扩展问题就是求最短路径等问题。
  这里给一个简单的无向图
它的广度优先搜索的路径是 ABCDEF，当然搜索也是不唯一的。
模板 需要队列queue

def bfs(graph,s)//graph是一个图，s是指定的根节点
{
   //需要一个队列
   queue<int> q;
   q.push(s);
   //维护一个vis数组，记录图中的元素是否被使用过
   vector<int> vis;
   while(!q.empty())
   {
      vertex=q.front();
      q.pop();
      //提取连接vertex的所有边
      edges[]=graph(vertex)；
      for (auto e:edges)
      {
         if(e is not in vis)
            {
               q.push(e);
               vis.push_back(e);
            }
      }
      print(vertex)
   }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

2 dfs

一条路走到黑，简单理解就是树的先根遍历，是其的推广。

  它的深度优先搜索的路径是 ABDFEC，当然搜索也是不唯一的。dfs模板一般用的比较少，大多数是使用递归，需要进行回溯。我们这里给出的模板只适合图的深搜,和上面的类似，只是将队列改为栈
模板 需要栈

def dfs(graph,s)//graph是一个图，s是指定的根节点
{
   //需要一个栈
   stack<int> q;
   q.push(s);
   //维护一个vis数组，记录图中的元素是否被使用过
   vector<int> vis;
   while(!q.empty())
   {
      vertex=q.top();
      q.pop();
      //提取连接vertex的所有边
      edges[]=graph(vertex)；
      for (auto e:edges)
      {
         if(e is not in vis)
            {
               q.push(e);
               vis.push_back(e);
            }
      }
      print(vertex)
   }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

3 二叉树的层次遍历

  给定一个二叉树，如果只是打印层次的节点，则可以直接想到bfs，需要队列，因为二叉树只有根节点和子节点，不牵扯重复访问的问题，所以不需要vis数组记录代码如下

 vector<int> levelOrder(TreeNode* root) {
         //bfs大法  队列
         vector<int> ans;
         if(root==NULL)
         return ans;
         queue<TreeNode*> que;
         que.push(root);
         while(!que.empty())
         {
             TreeNode *tmp=que.front();
             que.pop();
             ans.push_back(tmp->val);
             if(tmp->left!=NULL) que.push(tmp->left);
             if(tmp->right!=NULL) que.push(tmp->right);
         }
         return ans;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

leetcode32题，但如果题目这样要求，从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
        3
        /  \
       9  20
        / \
      15   7
需要返回[[3],[9,20],[15,7]],形如vector<vector>这样的二维数组
两种方法都可以使用
bfs

   vector<vector<int> > levelOrder(TreeNode* pRoot) {
          if(pRoot==NULL)
              return {};
            vector<vector<int> > ans;
            queue<TreeNode*> q;
            q.push(pRoot);
            while(!q.empty()){
                int size=q.size();
                vector<int> nans(size,0);
                for(int i=0;i<size;i++)
                {
                    TreeNode* tmp=q.front();
                    q.pop();
                    nans[i]=tmp->val;
                    if(tmp->left)
                       q.push(tmp->left);
                    if(tmp->right)
                       q.push(tmp->right);
                }
                ans.push_back(nans);
            }
            return ans;
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

当然，也可以将depth转换为pair, 使用pair(TreeNode*,int depth)的结构

 vector<vector<int>> levelOrder(TreeNode* root) {
          //bfs大法，和之前普通的层序遍历差不多，只需要加入一个depth队列记录层数
           vector<vector<int>> ans;
           if(root==NULL)
           return ans;
           queue<pair<TreeNode*, int>> que;//ThreeNode*代表节点，int代表层数
           que.push(make_pair(root,0));
           while(!que.empty())
           {
               TreeNode* tmp=que.front().first;
               int d=que.front().second;  
               que.pop();
               if(d==ans.size())
               ans.emplace_back();
               ans[d].push_back(tmp->val);
               if(tmp->left!=NULL)  
               {
                   que.push(make_pair(tmp->left,d+1)); 
               }
               if(tmp->right!=NULL) 
               {
                   que.push(make_pair(tmp->right,d+1)); 
               }
           }
           return ans;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

dfs,直接使用递归

 vector<vector<int>> ans;
   void dfs(TreeNode* t,int dep)
   {
       if(t==NULL)
       return ;
       if(ans.size()==dep)
              ans.emplace_back();
       ans[dep].push_back(t->val);
       dfs(t->left,dep+1);
       dfs(t->right,dep+1);
   }
    vector<vector<int>> levelOrder(TreeNode* root) {
          //dfs大法
          dfs(root,0);
          return ans;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16