广度优先搜索

广度优先搜索概念可自行查阅

用二叉树的层序遍历会容易理解很多，如图

层序遍历怎么实现呢要用到队列(先进先出)：

102. 二叉树的层序遍历 - 力扣（LeetCode）

这个题的一个难点就是你要把每一层的元素分开，一个一维数组里放一层元素，在C语言写法里可以设一个last参数记录上一层遍历结束时的rear值，这样last与front之差即上一层元素的个数

c++写法就简单一些，上一层元素个数即队列的大小

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     struct TreeNode *left;
 6  *     struct TreeNode *right;
 7  * };
 8  */
 9 
10 
11 /**
12  * Return an array of arrays of size *returnSize.
13  * The sizes of the arrays are returned as *returnColumnSizes array.
14  * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
15  */
16 int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
17     *returnSize = 0;
18     if(root == NULL)
19      return NULL;
20     int** res = malloc(sizeof(int *)*2000);
21     *returnColumnSizes = malloc(sizeof(int )*2000);
22     struct TreeNode* queue[2000];
23     int rear = 0,front = 0;
24     queue[rear ++] = root;
25     while(front < rear){
26         int last = rear;
27         int col = 0;
28         res[*returnSize] = malloc(sizeof(int )*(last - front));
29         struct TreeNode* cur;
30         for(;front < last;){   //可以改为while(front < last)，emm...我个人更喜欢for循环 因为时间效率高一点
31           cur = queue[front ++];
32           res[(*returnSize)][col ++] = cur -> val;
33           if(cur -> left)
34            queue[rear ++] = cur -> left;
35           if(cur -> right)
36            queue[rear ++] = cur -> right;
37           
38         }
39             (*returnColumnSizes)[(*returnSize)++] = col;
40     }
41     return res;
42 }

c++

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 8  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 9  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10  * };
11  */
12 class Solution {
13 public:
14     vectorint>> levelOrder(TreeNode* root) {
15       vectorint> > res;
16       if(! root)
17        return res;
18       queue q;
19       q.push(root);
20       while(!q.empty()){
21          res.push_back(vector<int>());
22          int col = q.size();
23          for(int i = 0;i < col;i ++){
24              auto cur = q.front();
25              q.pop();
26              res.back().push_back(cur -> val);
27              if(cur -> left)
28               q.push(cur -> left);
29              if(cur -> right)
30               q.push(cur -> right);
31          }
32       }
33       return res;
34     }
35 };

广度优先搜索

相关

标签