打卡打卡

12/31/2021
Lowest Common Ancestor of a Binary Tree
DFS -  通过最先找到的左右/根节点来判断最小祖先

1/1/2022
Lowest Common Ancestor III
DFS

1/1/2021
Flatten Binary Tree to Linked List
DFS

1/2/2022
Kth Smallest Element in a BST
iterator模拟栈，模拟dfs进行遍历直到栈顶pop到第k-1个元素
有的题需要游走的话需要iterator实现左右走

1/8/2022
Permutations
DFS - 递归增加未访问的和剔除访问过的找新的permutation

1/9/2022
Traveling Salesman Problem
DFS 构建图 dict in dict/ hashmap in hashmap

补充内容 (2022-01-09 18:57 +8:00):
时间复杂度超时

1/9/2021
Permutations 理解
全排列 图形An ^n
代码里面dfs：递归的定义是一直往里面加到全集，递归的出口是长度等于数组，避免重复用visited统计。加到底之后，去除加过的数字，然后继续dfs其他数。每一次递归出口的时候把数据集加进总集合。

1/13/2021
TSP
Permutation DFS
理解：最后出口的时候打擂台比较全排列找到最小路径，和枚举全排列同样的道理
需要额外构建图当作参数传进dfs
需要构建类去避免float('inf')初始化的deep copy，避免内层函数的修改在外层不生效，无法直接传参

1/14/2022
TSP DFS 剪枝优化
类似于构图，在寻找路径的时候每个点分别反转最后一个点与新点的连接大小比较的逻辑(中间点已经试过了不用再试)，可以去掉一些明显错误的路径，相较于暴力dfs的一种优化。剪枝只是剪去了当前加入点中明显错误的部分，因为还没有加入其他点所以不代表唯一最优，还是需要dfs出口的时候打擂台进行最小预算的比较

补充内容 (2022-01-16 12:24 +8:00):
时间复杂度还是n! * n = 全排列数 * 构造函数数

1/16/2022
TSP DFS 动态规划
把路径中的点存成二进制，利用异或操作判断是否访问过，利用二维数组记录新加入的点预算与之前每个点预算，和直接用原来路径加入新的点，进行比较，返回f[state_size - 1]最小值。时间复杂度优化到 2 ^ n * n ^ 2，指数比阶乘时间复杂度低

这个解法不记录具体路径所以降低时间复杂度（状态压缩），即点是如何连接的，但是在比较较小值中计算保留