二叉树的层序遍历

给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。

题目地址

这题其实并不难,但是我第一次提交的代码只超过了20%的人

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
27
28
29
30
31
32
33
34
35
36
class Solution
{
public:
vector<vector<int>> levelOrder(TreeNode* root)
{
vector<vector<int>> result;
queue<TreeNode*> nodeQueue; // 这个队列存放了每一层的节点,按照从左到右的顺序
TreeNode* node;
if (!root) return result;

nodeQueue.push(root);
while (!nodeQueue.empty()) // 从这里开始取出每一层的节点进行操作
{
result.push_back(vector<int>()); // 添加新的一层
int itemSize = nodeQueue.size();

for (int i = 0; i < itemSize; i++) // 将该层所有的节点取出
{
node = nodeQueue.front();
result.back().push_back(node->val);
nodeQueue.pop();
if (node->left) {

nodeQueue.push(node->left);

}
if (node->right) {

nodeQueue.push(node->right);
}

}
}
return result;
}
};

岛屿数量

给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。

岛屿总是被水包围,并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。

此外,你可以假设该网格的四条边均被水包围。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
输入:
[
['1','1','1','1','0'],
['1','1','0','1','0'],
['1','1','0','0','0'],
['0','0','0','0','0']
]
输出: 1

输入:
[
['1','1','0','0','0'],
['1','1','0','0','0'],
['0','0','1','0','0'],
['0','0','0','1','1']
]
输出: 3
解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。

题目

以下是我的解法,比较简陋,速度也不是很快,仅仅是使用搜索而已

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
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int res = 0;
for (int i = 0; i < grid.size(); i++)
{
for (int j = 0; j < grid[i].size(); j++)
{
if (grid[i][j] == '1') {
visit(grid, i, j);
res++;
}
}
}

return res;

}

void visit(vector<vector<char>>& grid, int i, int j) {
if (i >= grid.size() || i < 0) // 越界判断
{
return;
}
if (j >= grid[i].size() || j < 0)
{
return;
}

if (grid[i][j] == '1') {
grid[i][j] = 0;
visit(grid, i + 1, j); // 搜索附近
visit(grid, i - 1, j);
visit(grid, i, j + 1);
visit(grid, i, j - 1);
}
}
};