难度中等423
给定一个二叉树，返回其节点值自底向上的层序遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
例如：
给定二叉树[3,9,20,null,null,15,7],3 / \ 9 20 / \ 15 7返回其自底向上的层序遍历为：
[ [15,7], [9,20], [3] ]
在102基础上直接翻转就可以得到https://blog.csdn.net/sereasuesue/article/details/115445741
class Solution:
def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
result = []
if root is None:
return result
q = deque([])
q.append(root)
while len(q) > 0:
size = len(q)
level = []
while size > 0:
cur = q.popleft()
level.append(cur.val)
if cur.left is not None:
q.append(cur.left)
if cur.right is not None:
q.append(cur.right)
size = size - 1
result.append(level)
result.reverse()
return result
难度中等1076
给你一个由
'1'（陆地）和'0'（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。示例 1：
输入：grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] 输出：1示例 2：
输入：grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] 输出：3
BFS
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if grid is None or len(grid) == 0:
return 0
result = 0
row = len(grid)
col = len(grid[0])
queue = []
for i in range(0, row):
for j in range(0, col):
if grid[i][j] == '1':
result = result + 1
queue.append([i,j])
grid[i][j] = '0'
while len(queue) > 0:
cur = queue.pop()
x = cur[0]
y = cur[1]
if x-1 >= 0 and grid[x-1][y] == '1':
queue.append([x-1, y])
grid[x-1][y] = '0'
if y-1 >= 0 and grid[x][y-1] == '1':
queue.append([x, y-1])
grid[x][y-1] = '0'
if x+1 < row and grid[x+1][y] == '1':
queue.append([x+1, y])
grid[x+1][y] = '0'
if y+1 < col and grid[x][y+1] == '1':
queue.append([x, y+1])
grid[x][y+1] = '0'
return resultdfs
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if grid is None or len(grid) == 0:
return 0
result = 0
row = len(grid)
col = len(grid[0])
for i in range(0, row):
for j in range(0, col):
if grid[i][j] == '1':
result = result + 1
self.dfs(grid, i, j, row, col)
return result
def dfs(self, grid, x, y, row, col):
if x < 0 or y < 0 or x >= row or y >= col or grid[x][y] == '0':
return
grid[x][y] = '0'
self.dfs(grid, x - 1, y, row, col)
self.dfs(grid, x + 1, y, row, col)
self.dfs(grid, x, y - 1, row, col)
self.dfs(grid, x, y + 1, row, col)
class Solution:
# Leetcode 200. Number of Islands
# Union Find
# R is the row of grid
# C is the column of grid
# Time Complexity: O(RC)
# Space Complexity: O(RC)
def numIslands(self, grid: List[List[str]]) -> int:
if grid is None or len(grid) == 0:
return 0
row = len(grid)
col = len(grid[0])
waters = 0
uf = UnionFind(grid)
for i in range(0, row):
for j in range(0, col):
if grid[i][j] == '0':
waters += 1
else:
directions = [(0,1), (0,-1), (-1,0), (1,0)]
for x, y in directions:
x = x + i
y = y + j
if x>=0 and y>=0 and x<row and y<col and grid[x][y] == '1':
uf.union(x*col+y, i*col+j)
return uf.getCount() - waters
class UnionFind:
def __init__(self, grid):
row = len(grid)
col = len(grid[0])
self.root = [-1]*(row*col)
self.count = row*col
for i in range(0, row*col):
self.root[i] = i
def find(self, x):
if x == self.root[x]:
return self.root[x]
else:
self.root[x] = self.find(self.root[x])
return self.root[x]
def union(self, x, y):
rootX = self.find(x)
rootY = self.find(y)
if rootX != rootY:
self.root[rootX] = rootY
self.count -= 1
def getCount(self):
return self.countself.root[rootX] = rootY
视频讲解https://www.bilibili.com/video/BV1sy4y1q79M?p=69
版权声明：本文为sereasuesue原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。