二叉树
36. 二叉树的中序遍历
递归就不写了，写一下迭代法
class Solution(object):
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if not root:
return
res = []
cur = root
stack = []
while cur or stack:
if cur:
stack.append(cur)
cur = cur.left
else:
cur = stack.pop()
res.append(cur.val)
cur = cur.right
return res
顺便再写一下前序和后序的迭代法
前序：
class Solution(object):
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if not root:
return
st = [root]
res = []
# cur =
while st:
cur = st.pop()
res.append(cur.val)
if cur.right:
st.append(cur.right)
if cur.left:
st.append(cur.left)
return res
后序：
class Solution(object):
def postorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if not root:
return
cur = root
st = []
prev = None
res = []
while st or cur:
if cur:
st.append(cur)
cur = cur.left
else:
cur = st.pop()
#现在需要确定的是是否有右子树，或者右子树是否访问过
#如果没有右子树，或者右子树访问完了，也就是上一个访问的节点是右子节点时
#说明可以访问当前节点
if not cur.right or cur.right == prev:
res.append(cur.val)
prev = cur
cur = None
else:
st.append(cur)
cur = cur.right
return res
37. 二叉树的最大深度
分解很简单，直接交给递归函数。但是遍历的思路都要会
- 分解（动态规划思路）
class Solution(object):
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
- 遍历（回溯思路）
走完之后depth-1
class Solution(object):
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
def helper(root):
if not root:
self.res = max(self.res, self.depth)
return
self.depth += 1
helper(root.left)
helper(root.right)
self.depth -= 1
self.depth = 0
self.res = 0
helper(root)
return self.res
- 延伸：可否不用递归来做这道题？
这个解法是chatgpt写的，将depth和node一起压入栈，避免对depth +1， -1的操作
class Solution(object):
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
stack = [(root, 1)]
max_depth = 0
while stack:
node, depth = stack.pop()
if node:
max_depth = max(max_depth, depth)
if node.right:
stack.append((node.right, depth + 1))
if node.left:
stack.append((node.left, depth + 1))
return max_depth
- 反转二叉树
递归函数的定义：给定二叉树根节点，反转它的左右子树。
后续位置递归
class Solution(object):
def invertTree(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
if not root:
return
self.invertTree(root.left)
self.invertTree(root.right)
root.left, root.right = root.right, root.left
return root
- 对称二叉树
核心思路：
如果一个树的左子树与右子树镜像对称，那么这个树是对称的。该问题可以转化为：两个树在什么情况下互为镜像？
如果同时满足下面的条件，两个树互为镜像： - 它们的两个根结点具有相同的值
- 每个树的右子树都与另一个树的左子树镜像对称
创建一个函数，传入2个节点，判断是否对称
class Solution(object):
def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
def check(p, q):
if p and q:
a = p.val == q.val
b = check(p.left, q.right)
c = check(p.right, q.left)
return a and b and c
elif (not p) and (not q):
return True
else:
return False
return check(root, root)
40 二叉树的直径
class Solution(object):
def diameterOfBinaryTree(self, root):
"""
:type root: TreeNode
:rtype: int
"""
def helper(root):
if not root:
return 0
l = helper(root.left)
r = helper(root.right)
d = max(l, r) + 1
self.res = max(self.res, l + r)
return d
self.res = 0
helper(root)
return self.res
41. 二叉树的层序遍历
class Solution(object):
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if not root:
return
q = [root]
res = []
while q:
sz = len(q)
temp = []
for i in range(sz):
cur = q.pop(0)
temp.append(cur.val)
if cur.left:
q.append(cur.left)
if cur.right:
q.append(cur.right)
res.append(temp[:])
return res
42. 构造二叉搜索树
有序数组，找到mid，nums[mid]是根节点，左边和右边分别是左子树和右子树
class Solution(object):
def sortedArrayToBST(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
def construct(nums, lo, hi):
if lo > hi:
return
mid = lo + (hi-lo)//2
root = TreeNode(nums[mid])
root.left = construct(nums, lo, mid-1)
root.right = construct(nums, mid+1, hi)
return root
if not nums:
return
n = len(nums)
return construct(nums, 0, n-1)
43. 判断二叉搜索树
迭代法写中序遍历
class Solution(object):
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if not root:
return True
prev = None
st = []
cur = root
while st or cur:
if cur:
st.append(cur)
cur = cur.left
else:
cur = st.pop()
if prev and prev.val >= cur.val:
return False
prev = cur
cur = cur.right
return True
44. bst第k小元素
迭代法遍历，太爽了
class Solution(object):
def kthSmallest(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: int
"""
st = []
cur = root
i = 0
while st or cur:
if cur:
st.append(cur)
cur = cur.left
else:
cur = st.pop()
i += 1
if i == k:
return cur.val
cur = cur.right
45. 二叉树的右视图
层序遍历，从右往左
class Solution(object):
def rightSideView(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if not root:
return
q = deque()
q.append(root)
res = []
while q:
sz = len(q)
res.append(q[0].val)
for i in range(sz):
cur = q.popleft()
if cur.right:
q.append(cur.right)
if cur.left:
q.append(cur.left)
return res
46. 二叉树展开为链表
class Solution(object):
def flatten(self, root):
"""
:type root: TreeNode
:rtype: None Do not return anything, modify root in-place instead.
"""
if not root:
return
l = self.flatten(root.left)
r = self.flatten(root.right)
root.left = None
root.right = l
node = root
while node.right:
node = node.right
node.right = r
return root
47. 从前序和中序构造二叉树
class Solution(object):
def buildTree(self, preorder, inorder):
"""
:type preorder: List[int]
:type inorder: List[int]
:rtype: TreeNode
"""
def helper(preorder, prelo, prehi, inorder, inlo, inhi):
if prelo > prehi or inlo > inhi:
return
root_val = preorder[prelo]
root_idx = inorder.index(root_val)
left_size = root_idx - inlo
root = TreeNode(root_val)
root.left = helper(preorder, prelo+1, prelo+left_size, inorder, inlo, root_idx-1)
root.right = helper(preorder, prelo+left_size+1, prehi, inorder, root_idx+1, inhi)
return root
n = len(preorder)
return helper(preorder, 0, n-1, inorder, 0, n-1)
48. 路径总和III
后序遍历，helper返回以root为开始的路径和的哈希表
class Solution(object):
def pathSum(self, root, targetSum):
"""
:type root: TreeNode
:type targetSum: int
:rtype: int
"""
def helper(root):
if not root:
return {}
l = helper(root.left)
r = helper(root.right)
res = {}
for k, v in l.items():
x = root.val + k
res[x] = v
for k, v in r.items():
x = root.val + k
res[x] = res.get(x, 0) + v
res[root.val] = res.get(root.val, 0) + 1
self.cnt += res.get(targetSum, 0)
return res
self.cnt = 0
x = helper(root)
return self.cnt
49. 二叉树的最近公共祖先
思路：如果一个节点能够在它的左右子树中分别找到 p 和 q，则该节点为 LCA 节点。
class Solution(object):
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
def helper(root, p, q):
if not root:
return
# 说明p或者q本身就是LCA
if root == p or root == q:
return root
left = helper(root.left, p, q)
right = helper(root.right, p, q)
if left and right:
# 说明p和q一个在左子树，另一个在右子树，root就是LCA
return root
return left if left else right
return helper(root, p, q)
50. 二叉树的最大路径和
自己ac的hard题目。
class Solution(object):
def maxPathSum(self, root):
"""
:type root: TreeNode
:rtype: int
"""
def helper(root):
if not root:
return 0
leftMax = helper(root.left)
rightMax = helper(root.right)
x = max(root.val, root.val+leftMax, root.val+rightMax)
self.res = max(self.res, x, root.val+leftMax+rightMax)
return x
self.res = -1001
helper(root)
return self.res
图论
51. 岛屿数量
dfs
class Solution(object):
def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
def dfs(grid, i, j):
m, n = len(grid), len(grid[0])
if i < 0 or i >= m or j < 0 or j >= n:
return
if grid[i][j] == "0":
return
grid[i][j] = "0"
dfs(grid, i+1, j)
dfs(grid, i-1, j)
dfs(grid, i, j+1)
dfs(grid, i, j-1)
m, n = len(grid), len(grid[0])
res = 0
for i in range(m):
for j in range(n):
if grid[i][j] == "1":
dfs(grid, i, j)
res += 1
return res
52 腐烂橘子
来自 作者：nettee的题解
返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。翻译一下，实际上就是求腐烂橘子到所有新鲜橘子的最短路径。要用bfs
一开始，我们找出所有腐烂的橘子，将它们放入队列，作为第 0 层的结点。
然后进行 BFS 遍历，每个结点的相邻结点可能是上、下、左、右四个方向的结点，注意判断结点位于网格边界的特殊情况。
由于可能存在无法被污染的橘子，我们需要记录新鲜橘子的数量。在 BFS 中，每遍历到一个橘子（污染了一个橘子），就将新鲜橘子的数量减一。如果 BFS 结束后这个数量仍未减为零，说明存在无法被污染的橘子
class Solution(object):
def orangesRotting(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
m, n = len(grid), len(grid[0])
q = deque()
fresh_cnt = 0
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
fresh_cnt += 1
elif grid[i][j] == 2:
q.append((i, j))
res = 0
while fresh_cnt > 0 and q:
res += 1
sz = len(q)
for i in range(sz):
cur = q.popleft()
i, j = cur[0], cur[1]
if i > 0 and grid[i-1][j] == 1:
q.append((i-1, j))
grid[i-1][j] = 2
fresh_cnt -= 1
if i < m-1 and grid[i+1][j] == 1:
q.append((i+1, j))
grid[i+1][j] = 2
fresh_cnt -= 1
if j > 0 and grid[i][j-1] == 1:
q.append((i, j-1))
grid[i][j-1] = 2
fresh_cnt -= 1
if j < n-1 and grid[i][j+1] == 1:
q.append((i, j+1))
grid[i][j+1] = 2
fresh_cnt -= 1
if fresh_cnt == 0:
return res
else:
return -1
53. 课程表
自己写的暴力解法：
class Solution(object):
def canFinish(self, numCourses, prerequisites):
"""
:type numCourses: int
:type prerequisites: List[List[int]]
:rtype: bool
"""
d = {}
for i in prerequisites:
a, b = i[0], i[1]
if a not in d:
d[a] = [b]
else:
d[a].append(b)
learned = set()
while len(learned) < numCourses:
L = len(learned)
# print(learned, x)
for n in range(numCourses):
if n not in d:
learned.add(n)
else:
flag = True
for x in d[n]:
if x not in learned:
flag = False
break
if flag:
learned.add(n)
# print(learned, x)
if len(learned) == L:
return False
return True
看题解：有向图+bfs。用一个in_degree数组存储每个节点（每节课）的入度，再用一个map d存储每个节点的出度。
每次入度为0的课程入队，bfs的思路。
class Solution(object):
def canFinish(self, numCourses, prerequisites):
"""
:type numCourses: int
:type prerequisites: List[List[int]]
:rtype: bool
"""
d = {}
in_degree = [0] * numCourses
for i in prerequisites:
a, b = i[0], i[1]
in_degree[a] += 1
if b not in d:
d[b] = [a]
else:
d[b].append(a)
q = deque()
for n in range(numCourses):
if in_degree[n] == 0:
q.append(n)
cnt = 0
while q:
cur = q.popleft()
cnt += 1
if cur in d:
for k in d[cur]:
in_degree[k] -= 1
if in_degree[k] == 0:
q.append(k)
return cnt == numCourses
54. Trie前缀树
面试大概率不会考，跳过