98. 验证二叉搜索树

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
class Solution(object):
def isValidBST(self, root):
"""
:type root: Optional[TreeNode]
:rtype: bool
"""
self.prev_val = -float('inf')
return self.inorder_check(root)

def inorder_check(self, node):
if node is None:
return True

if self.inorder_check(node.left) is False:
return False

if node.val <= self.prev_val:
return False

self.prev_val = node.val

if self.inorder_check(node.right) is False:
return False

return True

230. 二叉搜索树中第 K 小的元素

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
class Solution(object):
def kthSmallest(self, root, k):
"""
:type root: Optional[TreeNode]
:type k: int
:rtype: int
"""
res = []
stack = []

current = root
while current or stack:

while current:
stack.append(current) #
current = current.left

current = stack.pop()
res.append(current.val)

current = current.right

# res.sort() 对于二叉搜索树来说左树的节点一定小于根,右树节点一定大于根

return res[k-1]

199. 二叉树的右视图

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
import collections
class Solution(object):
def rightSideView(self, root):
"""
:type root: Optional[TreeNode]
:rtype: List[int]
"""
# 题目里二叉树的节点范围是[0,100],它为0的时候就是none,不能忽略这种情况
if root is None:
return []

queue = collections.deque([root])
res = []
while queue:
level_size = len(queue)

for i in range(level_size):

node = queue.popleft()

if i == level_size-1:
res.append(node.val)

if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)

return res

114. 二叉树展开为链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
def flatten(self, root):
"""
:type root: Optional[TreeNode]
:rtype: None Do not return anything, modify root in-place instead.
"""
if root is None:
return

self.flatten(root.left)
self.flatten(root.right)

# 后序遍历,先遍历了左右节点再遍历根节点
# 先把所有节点的右子树先剪下来存好,再把左子树接到右边,把左子树置空,
# 最后跑到新的右子树最后把之前减下来的右子树粘上去
orignal_right = root.right
root.right = root.left
root.left = None
node = root

while node.right:
node = node.right

node.right = orignal_right

105. 从前序与中序遍历序列构造二叉树

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
class Solution(object):
def buildTree(self, preorder, inorder):
"""
:type preorder: List[int]
:type inorder: List[int]
:rtype: Optional[TreeNode]
"""
self.inorder_map = {}
for idx, val in enumerate(inorder):
self.inorder_map.update({val: idx})

self.preorder_index = 0

return self.build(preorder, 0, len(inorder)-1)

def build(self, preorder, inorder_left, inorder_right):
"""
这个函数负责在中序遍历的 [inorder_left, inorder_right] 范围内,
根据前序遍历的顺序,构建一棵树。
"""
if inorder_left > inorder_right:
return None

root_val = preorder[self.preorder_index]
self.preorder_index += 1

root = TreeNode(root_val)

inorder_root_index = self.inorder_map[root_val]

root.left = self.build(preorder, inorder_left, inorder_root_index - 1)
root.right = self.build(preorder, inorder_root_index + 1,inorder_right)

return root

236. 二叉树的最近公共祖先

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
class Solution(object):
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
# 终止条件: 1.当前节点为空
if root is None:
return None

# 终止条件:2.如果当前节点就是p或q,根据题意,节点自己可以作为它和它所有后代的祖先,直接返回
if root == q or root == p:
return root

left_report = self.lowestCommonAncestor(root.left, p, q)
right_report = self.lowestCommonAncestor(root.right, p, q)

# 如果p和q在根节点的两边,那么根节点自己就是祖先
if left_report and right_report:
return root

# 如果只有一边有汇报,说明pq都在那一边,就把那一边传回去
if left_report:
return left_report

if right_report:
return right_report

# 如果都没汇报,那就说明这个子树里啥都没有
return None

124. 二叉树中的最大路径和

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
class Solution(object):
def maxPathSum(self, root):
"""
:type root: Optional[TreeNode]
:rtype: int
"""
self.max_path_sum = -float('inf')

self.compute(root)

return self.max_path_sum

def compute(self, node):

if node is None:
return 0 # 不是None,空节点贡献为0

# 父节点的计算或决策,必须依赖其左右子树的完整计算结果。
# 后序遍历,并且只要节点是正的值,所以要把结果和0比较
left_gain = self.compute(node.left)
left_gain = max(0, left_gain)
right_gain = self.compute(node.right)
right_gain = max(0, right_gain)

# 遍历完后,第一次肯定到最左边的叶子节点,先计算它的val再加上它的左右子树的gain(None)
curr_path_sum = node.val + left_gain + right_gain
# 得到了节点的和就记下来,不断更新直到遍历完成后留下的值自然是最大值
self.max_path_sum = max(self.max_path_sum, curr_path_sum)

# 返回值也很重要,返回的时候就是当前节点的val,
# 注意这个max是用来单向决定接下来往哪走的,如果都返回不就成了左右分叉的样子了,
# 所以得算出来哪边最大然后沿着它走
return node.val + max(left_gain, right_gain)

200. 岛屿数量

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
class Solution(object):
def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
if grid is None or grid[0] is None:
return

row, col = len(grid), len(grid[0])

islands_count = 0

def dfs(r,c):
if not (0 <= r < row and 0 <= c < col and grid[r][c] == '1'):
return

grid[r][c] = '0' #

dfs(r - 1, c)
dfs(r + 1, c)
dfs(r, c - 1)
dfs(r, c + 1)

for r in range(row): #
for c in range(col):
if grid[r][c] == '1': #
islands_count += 1
dfs(r, c) #

return islands_count

994. 腐烂的橘子

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
import collections
class Solution(object):
def orangesRotting(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
# 思路:这题必须用bfs,dfs的实现方式不符合这题,首先使用队列把腐烂的橘子都装进去,
# 需要先遍历整个图,同时找出还有多少新鲜的橘子,用变量记录,
# 以及设定有没有发生腐烂的标记,用来判断minute是否需要+1
row, col = len(grid), len(grid[0])
queue = collections.deque()
fresh_count = 0
for r in range(row):
for c in range(col):
if grid[r][c] == 2:
queue.append((r, c)) #
elif grid[r][c] == 1:
fresh_count += 1

# 记录完成后先判断有没有新鲜的橘子,没有就跳出
if fresh_count == 0:
return 0

# 定义分钟数
minutes = 0
# 定义侦察兵的方向,通过循环来移动它,这里是通过它来腐烂其他橘子
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

while queue:
level_size = len(queue)
#定义腐烂信号,让minutes能够正确更新
rotted_in_this_min = False

# 这个循环忘记了,不要忘记层次遍历的目的,需要通过for来取出queue的元素
for _ in range(level_size):
(r, c) = queue.popleft() # rotted_orange的坐标直接取出来了
for (dr, dc) in directions:
# 将位置坐标直接相加,配合for循环实现上下左右一个单位的遍历和操作
new_r, new_c = dr + r, dc + c

# 忘记判断了,需要先判断相邻的位置是否合法以及是否有新鲜橘子
if 0 <= new_r < row and 0 <= new_c < col and grid[new_r][new_c] == 1:
# 感染新鲜橘子!
grid[new_r][new_c] = 2
# 同时加入
queue.append((new_r, new_c))
fresh_count -= 1
rotted_in_this_min = True

# 注意在while里面更新分钟数
if rotted_in_this_min:
minutes += 1

# 最后是判断结果
# 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数, 也就是如果新鲜橘子没了就结束,
# 如果到最后还有感染不到的新鲜橘子就返回-1
if fresh_count == 0:
return minutes
else:
return -1