二叉树的层序遍历

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

题目地址

这题其实并不难，但是我第一次提交的代码只超过了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);
		}
	}
};