[102] Binary Tree Level Order Traversal [Medium-Easy]
[107] Binary Tree Level Order Traversal II [Medium-Easy]
这俩题没啥区别。都是二叉树层级遍历。BFS做。
可以用一个队列或者两个队列实现。我觉得一个队列实现的更好。（一个队列实现的重点是利用队列的size来看当前层级的节点数）
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ans;
if (!root) {
return ans;
}
queue<TreeNode *> q;
q.push(root);
while (!q.empty()) {
size_t sz = q.size();
vector<int> level;
for (auto i = ; i < sz; ++i) {
TreeNode* cur = q.front();
q.pop();
level.push_back(cur->val);
if (cur->left) {
q.push(cur->left);
}
if (cur->right) {
q.push(cur->right);
}
}
ans.push_back(level);
}
return ans;
}
};
[101] Symmetric Tree [Easy]
判断一棵树是不是对称树。为啥还是不能一下子就写出来。。。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if (!root) return true;
return isSymmetric(root->left, root->right);
}
bool isSymmetric(TreeNode* left, TreeNode* right) {
if (!left && !right) {
return true;
}
else if (left == nullptr || right == nullptr) {
return false;
}
else if (left->val != right->val){
return false;
}
return isSymmetric(left->left, right->right) && isSymmetric(left->right, right->left);
} };
[542] 01 Matrix [Medium]
给个01矩阵，找到每个cell到 0 entry的最短距离。
从第一个0元素开始BFS, 用队列记录每个 0 元素的位置, 遍历队列，更新一个周围的元素之后，把更新的元素也进队。
队列一定是越来越短的，因为你每pop一个出来，需要更新元素才能push
class Solution {
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
vector<vector<int>> ans;
//const int m[4] = {1, 0, -1, 0}; //top - buttom
//const int n[4] = {0, 1, 0, -1}; //left - right
const vector<pair<int, int>> dir{{, }, {, }, {-, }, {, -}};
if (matrix.size() == || matrix[].size() == ) {
return ans;
}
const int rows = matrix.size(), cols = matrix[].size();
queue<pair<int, int>> q;
for (size_t i = ; i < rows; ++i) {
for (size_t j = ; j < cols; ++j) {
if (matrix[i][j] != ) {
matrix[i][j] = INT_MAX;
}
else {
q.push(make_pair(i, j));
}
}
}
while (!q.empty()) {
pair<int, int> xy = q.front();
q.pop();
for(auto ele: dir) {
int new_x = xy.first + ele.first, new_y = xy.second + ele.second;
if (new_x >= && new_x < rows && new_y >= && new_y < cols) {
if (matrix[new_x][new_y] > matrix[xy.first][xy.second] + ) {
matrix[new_x][new_y] = matrix[xy.first][xy.second] + ;
q.push({new_x, new_y});
}
}
}
}
return matrix;
}
};