当前位置：首页 > news >正文

leetcode刷题记录：hot100强化训练2：二叉树+图论

news 文章来源：https://blog.csdn.net/weixin_39548654/article/details/139705252 2024/11/7 7:50:05

二叉树

36. 二叉树的中序遍历

递归就不写了，写一下迭代法

class Solution(object):def inorderTraversal(self, root):""":type root: TreeNode:rtype: List[int]"""if not root:return res = []cur = rootstack = []while cur or stack:if cur:stack.append(cur)cur = cur.left                else:cur = stack.pop()res.append(cur.val)cur = cur.rightreturn res

顺便再写一下前序和后序的迭代法
前序：

class Solution(object):def preorderTraversal(self, root):""":type root: TreeNode:rtype: List[int]"""if not root:returnst = [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:returncur = rootst = []prev = Noneres = []while st or cur:if cur:st.append(cur)cur = cur.leftelse:cur = st.pop()#现在需要确定的是是否有右子树，或者右子树是否访问过#如果没有右子树，或者右子树访问完了，也就是上一个访问的节点是右子节点时#说明可以访问当前节点if not cur.right or cur.right == prev:res.append(cur.val)prev = curcur = Noneelse: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 0return 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)returnself.depth += 1helper(root.left)                                helper(root.right)               self.depth -= 1self.depth = 0self.res = 0helper(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 0stack = [(root, 1)]max_depth = 0while 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:returnself.invertTree(root.left) self.invertTree(root.right) root.left, root.right = root.right, root.leftreturn 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.valb = check(p.left, q.right)c = check(p.right, q.left)return a and b and celif (not p) and (not q):return Trueelse:return Falsereturn check(root, root)

40 二叉树的直径

class Solution(object):def diameterOfBinaryTree(self, root):""":type root: TreeNode:rtype: int"""def helper(root):if not root:return 0l = helper(root.left)r = helper(root.right)d = max(l, r)  + 1self.res = max(self.res, l + r)return dself.res = 0helper(root)return self.res

41. 二叉树的层序遍历

class Solution(object):def levelOrder(self, root):""":type root: TreeNode:rtype: List[List[int]]"""if not root:returnq = [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:returnmid = lo + (hi-lo)//2root = TreeNode(nums[mid])root.left = construct(nums, lo, mid-1)root.right = construct(nums, mid+1, hi)return rootif not nums:returnn = 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 Trueprev = Nonest = []cur = rootwhile st or cur:if cur:st.append(cur)cur = cur.leftelse:cur = st.pop()                if prev and prev.val >= cur.val:                    return Falseprev = curcur = cur.rightreturn True

44. bst第k小元素

迭代法遍历，太爽了

class Solution(object):def kthSmallest(self, root, k):""":type root: TreeNode:type k: int:rtype: int"""st = []cur = rooti = 0while st or cur:if cur:st.append(cur)cur = cur.leftelse:cur = st.pop()i += 1if i == k:return cur.valcur = cur.right

45. 二叉树的右视图

层序遍历，从右往左

class Solution(object):def rightSideView(self, root):""":type root: TreeNode:rtype: List[int]"""if not root:returnq = 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:returnl = self.flatten(root.left)r = self.flatten(root.right)    root.left = Noneroot.right = lnode = rootwhile node.right:node = node.rightnode.right = rreturn 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:returnroot_val = preorder[prelo] root_idx = inorder.index(root_val)left_size = root_idx - inloroot = 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 rootn = 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 + kres[x] = v              for k, v in r.items():x = root.val + kres[x] = res.get(x, 0) + vres[root.val] = res.get(root.val, 0) + 1self.cnt += res.get(targetSum, 0)return resself.cnt = 0x = 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本身就是LCAif root == p or root == q:return rootleft = helper(root.left, p, q)right = helper(root.right, p, q)   if left and right:# 说明p和q一个在左子树，另一个在右子树，root就是LCAreturn rootreturn 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 0leftMax = 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 xself.res = -1001helper(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 = 0for i in range(m):for j in range(n):if grid[i][j] == "1":dfs(grid, i, j)res += 1return 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 = 0for i in range(m):for j in range(n):if grid[i][j] == 1:fresh_cnt += 1elif grid[i][j] == 2:q.append((i, j))res = 0while fresh_cnt > 0  and q:res += 1sz = 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] = 2fresh_cnt -= 1 if i < m-1 and grid[i+1][j] == 1:q.append((i+1, j))grid[i+1][j] = 2fresh_cnt -= 1 if j > 0 and grid[i][j-1] == 1:q.append((i, j-1))grid[i][j-1] = 2fresh_cnt -= 1 if j < n-1 and grid[i][j+1] == 1:q.append((i, j+1))grid[i][j+1] = 2fresh_cnt -= 1     if fresh_cnt == 0:return reselse: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 = Truefor x in d[n]:if x not in learned: flag = Falsebreakif flag:learned.add(n)# print(learned, x)if len(learned) == L:return Falsereturn 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] * numCoursesfor i in prerequisites:            a, b = i[0], i[1]in_degree[a] += 1if 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 = 0while q:cur = q.popleft()cnt += 1if cur in d:for k in d[cur]:in_degree[k] -= 1if in_degree[k] == 0:q.append(k)return cnt == numCourses

54. Trie前缀树

面试大概率不会考，跳过

二叉树