二叉树 递归与迭代 深度优先遍历与广度优先遍历 二叉树深度 不遍历每个节点怎么知道深度？ 时间复杂度O(n) 二叉树天然是可以分解为小规模问题的问题，递

最小规模问题 突破口 range(n, -1, -1)

分出几步依次做 有序数组想双指针 动态规划想函数 表达该问题 递归想记忆化表格 函数值缓存，递归前先查表 递归有时比动态规划计算量小 从顶向下算需要的

记录 leetcode第78题子集 递归 直观，逐渐增加规模 class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: n = len(nums) output = [[]] for num in nums: output += [curr + [num] for curr in output] return output 回溯 全排列/组合/子集问题 class

动态数组 需要记录的状态是常数级 斐波那契数列通项公式 解析解，有精度误差 $$ f(n) = \frac 1 {\sqrt5} \bigg\lbrack\bigg(\frac {1 + \sqrt5} 2\bigg) ^ n - \bigg(\frac {1 - \sqrt5} 2\bigg) ^ n\bigg\rbrack $$ 矩阵快速幂 二分法，时间复杂度

获取链表长度 length = 1 ptr = head while ptr.next: ptr = ptr.next length += 1 给定一个链表，就要考虑为空的情况 给定一个非空链表 链表需要变量来在遍历的同时原地修改 也需要变量来找回整

递归优化 记录已经算过的 lru_cache、函数外字典、函数内字典、装饰器内数组 动态规划 小问题组合为大问题，由底向上，推荐 数学法 寻找公式直接计

设置变量的个数和含义不同解法思路的难易程度也不同 自然，经验

逆时针旋转90℃二维矩阵 list(zip(*matrix))[::-1] 被访问过visited

初识动态规划 leetcode第53题最大子序和 贪心小试牛刀 class Solution: def maxSubArray(self, nums: List[int]) -> int: ans = nums[0] res = ans for i in range(1, len(nums)): if ans <= 0: ans = nums[i] else: ans += nums[i] res = max(ans, res) return res 动态规划转