LeetCode Hot100 刷题笔记（4）—— 二叉树、图论
目录
一、二叉树
1. 二叉树的深度遍历（DFS：前序、中序、后序遍历）
2. 二叉树的最大深度
3. 翻转二叉树
4. 对称二叉树
5. 二叉树的直径
6. 二叉树的层序遍历
7. 将有序数组转换为二叉搜索树
8. 验证二叉搜索树
9. 二叉搜索树中第 K 小的元素
10. 二叉树的右视图
11. 二叉树展开为链表
12. 从前序与中序遍历序列构造二叉树
13. 路径总和 III
14. 二叉树的最近公共祖先
15. 二叉树中的最大路径和
二、图论
1. 岛屿数量
2. 腐烂的橘子
3. 课程表
4. 实现 Trie (前缀树)
前言
一、二叉树：二叉树的中序遍历，二叉树的最大深度，翻转二叉树，对称二叉树，二叉树的直径，二叉树的层序遍历，将有序数组转换为二叉搜索树，验证二叉搜索树，二叉搜索树中第 K 小的元素，二叉树的右视图，二叉树展开为链表，从前序与中序遍历序列构造二叉树，路径总和 III，二叉树的最近公共祖先，二叉树中的最大路径和。
二、图论：岛屿数量，腐烂的橘子，课程表，实现 Trie (前缀树)。
一、二叉树
1. 二叉树的深度遍历（DFS：前序、中序、后序遍历）
原题链接：94. 二叉树的中序遍历 - 力扣（LeetCode）
# （1）前序遍历：根-左-右
class Solution(object):def preorderTraversal(self, root):res = []def preorder(root):if not root:return res.append(root.val)preorder(root.left)preorder(root.right)preorder(root)return res# （2）中序遍历：左-根-右
class Solution(object):def inorderTraversal(self, root):res = []def inorder(root):if not root:return inorder(root.left)res.append(root.val)inorder(root.right)inorder(root)return res# （3）后序遍历：左-右-根
class Solution(object):def postorderTraversal(self, root):res = []def inorder(root):if not root:return postorder(root.left)postorder(root.right)res.append(root.val)postorder(root)return res2. 二叉树的最大深度
原题链接：104. 二叉树的最大深度 - 力扣（LeetCode）
class Solution(object):def maxDepth(self, root):if not root:return 0left_height = self.maxDepth(root.left)right_height = self.maxDepth(root.right)return max(left_height, right_height) + 13. 翻转二叉树
原题链接：226. 翻转二叉树 - 力扣（LeetCode）
class Solution(object):def invertTree(self, root):if not root:return root.left, root.right = root.right, root.leftself.invertTree(root.left)self.invertTree(root.right)return root4. 对称二叉树
原题链接：101. 对称二叉树 - 力扣（LeetCode）
class Solution(object):def isSymmetric(self, root):def check(left, right):if not left and not right:return Trueif not left or not right:return Falseif left.val != right.val:return Falsereturn check(left.left, right.right) and check(left.right, right.left)return check(root.left, root.right)5. 二叉树的直径
原题链接：543. 二叉树的直径 - 力扣（LeetCode）
class Solution(object):def diameterOfBinaryTree(self, root):def dfs(root):if not root:return 0, 0ld, ldepth = dfs(root.left)rd, rdepth = dfs(root.right)return max(ld, rd, ldepth+rdepth), max(ldepth, rdepth) + 1return dfs(root)[0]6. 二叉树的层序遍历
原题链接：102. 二叉树的层序遍历 - 力扣（LeetCode）
class Solution(object):def levelOrder(self, root):if not root:return []node = [root]res = []while len(node) > 0:res.append([i.val for i in node])node2 = []for i in node:if i.left:node2.append(i.left)if i.right:node2.append(i.right)node = node2return res7. 将有序数组转换为二叉搜索树
原题链接：108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）
class Solution(object):def sortedArrayToBST(self, nums):def dfs(left, right):if left > right:returnmid = (left + right) // 2root = TreeNode(nums[mid])root.left = dfs(left, mid-1)root.right = dfs(mid+1, right)return rootreturn dfs(0, len(nums)-1)8. 验证二叉搜索树
原题链接：98. 验证二叉搜索树 - 力扣（LeetCode）
class Solution(object):def isValidBST(self, root, left=float('-inf'), right=float('inf')):if not root:return Truex = root.valreturn left < x < right and self.isValidBST(root.left, left, x) and self.isValidBST(root.right, x, right)
# self.isValidBST(root.left, left, x)：遍历左子树，右边界更新
# self.isValidBST(root.right, x, right)：遍历右子树，左边界更新9. 二叉搜索树中第 K 小的元素
原题链接：230. 二叉搜索树中第 K 小的元素 - 力扣（LeetCode）
# 先通过前序/中序/后序遍历转为list，而后利用list属性找第k个小的元素。
# 此代码使用前序遍历（根-左-右）
class Solution(object):def kthSmallest(self, root, k):res = [] def preorder(root):if not root:returnres.append(root.val)preorder(root.left)preorder(root.right)return resres = preorder(root)res.sort()return res[k-1]10. 二叉树的右视图
原题链接：199. 二叉树的右视图 - 力扣（LeetCode）
class Solution(object):def rightSideView(self, root):# if len(res) == depth: res.append(root.val)# 先遍历右子树，再遍历左子树res = []def dfs(root, depth):if not root:return []if len(res) == depth:res.append(root.val)dfs(root.right, depth+1)dfs(root.left, depth+1)return resreturn dfs(root, 0)11. 二叉树展开为链表
原题链接：114. 二叉树展开为链表 - 力扣（LeetCode）
# 按 ‘根-左-右’ 的前序遍历顺序展开
class Solution(object):def flatten(self, root):self.prev = TreeNode()def preorder(root):if not root:return []left, right = root.left, root.rightself.prev.left = Noneself.prev.right = rootself.prev = self.prev.rightpreorder(left)preorder(right)return self.prevpreorder(root)12. 从前序与中序遍历序列构造二叉树
原题链接：105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）
class Solution(object):def buildTree(self, preorder, inorder):if not preorder or not inorder:returnroot = TreeNode(preorder[0])index = inorder.index(root.val)root.left = self.buildTree(preorder[1:1+index], inorder[:index])root.right = self.buildTree(preorder[1+index:], inorder[1+index:])return root13. 路径总和 III
原题链接：437. 路径总和 III - 力扣（LeetCode）
# self.right = right
class Solution(object):def pathSum(self, root, targetSum):if not root:return 0def dfs(root, targetSum):if not root:return 0if root.val == targetSum:ans = 1else:ans =0return ans + dfs(root.left, targetSum-root.val) + dfs(root.right, targetSum-root.val) # 根节点+遍历左子树+遍历右子树return dfs(root, targetSum) + self.pathSum(root.left, targetSum) + self.pathSum(root.right, targetSum) #路径 不需要从根节点开始，也不需要在叶子节点结束14. 二叉树的最近公共祖先
原题链接：236. 二叉树的最近公共祖先 - 力扣（LeetCode）
class Solution(object):def lowestCommonAncestor(self, root, p, q):if not root or root==p or root==q:return rootleft = self.lowestCommonAncestor(root.left, p, q)right = self.lowestCommonAncestor(root.right, p, q)if left and right:return rootif left:return leftreturn right15. 二叉树中的最大路径和
原题链接：124. 二叉树中的最大路径和 - 力扣（LeetCode）
class Solution(object):def maxPathSum(self, root):if not root:return 0self.maximum = float('-inf')def dfs(root):if not root:return 0l_val = dfs(root.left)r_val = dfs(root.right)self.maximum = max(self.maximum, l_val + r_val + root.val)return max(0, max(l_val, r_val) + root.val)dfs(root)return self.maximum二、图论
1. 岛屿数量
原题链接：200. 岛屿数量 - 力扣（LeetCode）
class Solution(object):def numIslands(self, grid):m, n = len(grid), len(grid[0])def dfs(grid, i, j):grid[i][j] = "0"for x, y in [[i+1, j], [i-1, j], [i, j+1], [i, j-1]]:if 0<=x<m and 0<=y<n and grid[x][y]=="1":grid[x][y] = "0"dfs(grid, x, y)res = 0for i in range(m):for j in range(n):if grid[i][j] == "1":res += 1dfs(grid, i, j) return res2. 腐烂的橘子
原题链接：994. 腐烂的橘子 - 力扣（LeetCode）
class Solution(object):def orangesRotting(self, grid):if not grid:return 0if 1 not in sum(grid, []):return 0m, n = len(grid), len(grid[0])queue = []time = 0for i in range(m):for j in range(n):if grid[i][j] == 2:queue.append([i, j, time])while queue:i, j, time = queue.pop(0)for x, y in [[i+1, j], [i-1, j], [i, j+1], [i, j-1]]:if 0<=x<m and 0<=y<n and grid[x][y]==1:grid[x][y] = 2queue.append([x, y, time+1])if 1 in sum(grid, []):return -1return time 3. 课程表
原题链接：207. 课程表 - 力扣（LeetCode）
# Python3实现本质是找有向无环图（无环：return True; 有环：return Flase）
class Solution:def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:from graphlib import TopologicalSorter as TSts = TS()for curr, pre in prerequisites:ts.add(curr, pre)return not ts._find_cycle() # 不存在有向无环图4. 实现 Trie (前缀树)
原题链接：208. 实现 Trie (前缀树) - 力扣（LeetCode）
class Trie(object):def __init__(self): self.lst = [] def insert(self, word):self.lst.append(word)def search(self, word):if word in self.lst:return Trueelse: return Falsedef startsWith(self, prefix):lp = len(prefix)for word in self.lst:if word[:lp] == prefix:return Truereturn False# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)