【LeetCode】BFS || DFS [2017.04.10--2017.04.17]

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

 1 class Solution {
 2 public:
 3     vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
 4         vector<vector<int>> ans;
 5         //const int m[4] = {1, 0, -1, 0}; //top - buttom
 6         //const int n[4] = {0, 1, 0, -1}; //left - right
 7         const vector<pair<int, int>> dir{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
 8         if (matrix.size() == 0 || matrix[0].size() == 0) {
 9             return ans;
10         }  
11         const int rows = matrix.size(), cols = matrix[0].size();
12         queue<pair<int, int>> q;
13         for (size_t i = 0; i < rows; ++i) {
14             for (size_t j = 0; j < cols; ++j) {
15                 if (matrix[i][j] != 0) {
16                     matrix[i][j] = INT_MAX;
17                 }
18                 else {
19                     q.push(make_pair(i, j));
20                 }
21             }
22         }
23         while (!q.empty()) {
24             pair<int, int> xy = q.front();
25             q.pop();
26             for(auto ele: dir) {
27                 int new_x = xy.first + ele.first, new_y = xy.second + ele.second;
28                 if (new_x >= 0 && new_x < rows && new_y >= 0 && new_y < cols) {
29                     if (matrix[new_x][new_y] > matrix[xy.first][xy.second] + 1) {
30                         matrix[new_x][new_y] = matrix[xy.first][xy.second] + 1;
31                         q.push({new_x, new_y});
32                     }           
33                 }
34             }
35         }
36         return matrix;
37     }
38 };