146 LRU缓存class LRUCache: def __init__(self, capacity: int): self.capacitycapacity self.cacheOrderedDict() def get(self, key: int) - int: if key not in self.cache:return -1 self.cache.move_to_end(key,False) return self.cache[key] def put(self, key: int, value: int) - None: self.cache[key]value self.cache.move_to_end(key,False) if len(self.cache)self.capacity: self.cache.popitem()543 二叉树的直径class Solution: def diameterOfBinaryTree(self, root: Optional[TreeNode]) - int: ans0 def dfs(node:Optional[TreeNode]) - int: if node is None:return 0 l_lendfs(node.left) r_lendfs(node.right) nonlocal ans ansmax(ans,l_lenr_len) return max(l_len,r_len)1 dfs(root) return ans108 将有序数组转换为二叉搜索树class Solution: def sortedArrayToBST(self, nums: List[int]) - Optional[TreeNode]: if not nums: return None mlen(nums)//2 leftself.sortedArrayToBST(nums[:m]) rightself.sortedArrayToBST(nums[m1:]) return TreeNode(nums[m],left,right)200 岛屿数量class Solution: def numIslands(self, grid: List[List[str]]) - int: ans0 m,nlen(grid),len(grid[0]) def dfs(i:int, j:int) - None: if i0 or j0 or im or jn or grid[i][j]!1:return if grid[i][j]1:grid[i][j]2 dfs(i-1,j) dfs(i1,j) dfs(i,j-1) dfs(i,j1) for i,row in enumerate(grid): for j,c in enumerate(row): if c1: dfs(i,j) ans1 return ans98 验证二叉搜索树class Solution: pre-inf def isValidBST(self, root: Optional[TreeNode]) - bool: if root is None:return True if not self.isValidBST(root.left):return False if root.valself.pre: return False self.preroot.val return self.isValidBST(root.right)