3.树 - 2.二叉树遍历（重点+基础） 递归遍历 前(先)序遍历：根-左-右 (1-2-4-5-7-8-3-6) 中序遍历：左-根-右 (4-2-7-8-5-1-3-6) 后序遍历：左-右-根 (4-8-7-5-2-6-3-1) 层次遍历：从上往下从左往右 (1,2,3,4,5,6,7,8) 反向构造

4.图 - 2.图的遍历 时间复杂度

对于Vue3 diff的讨论 vue3.0的diff 深度递归遍历vnode树，节点的标签和key相同认为是同一个节点则更新，不同则删除，然后处理子节点。 子节点分这几种情况处理：纯文本、vnode 数组和空 空往往意味着添加或删除； 纯文本相同直接更新innerText，不同则删除； 新旧子节点都是vnode数组则diff算法来处理； vue3.0 diff算法思想 编译模版时进行静态分析，标记动态节点，diff对比差异时仅对比动态节点（性能提升明显）； diff算法先去头去尾，借此缩短遍历对比数组长度（对数组插入和删除操作性能优化明显）； 通过对更新前后子节点数组建立映射表的方式，将O(n^2)复杂度的遍历降低到O(n)； 通过最长递增子序列方法了来diff前后的子节点数组，减少移动操作的次数； 最长递增子序列算法实现： /* 寻找最长递增子序列 使用动态规划思想，a -> c = a -> b + b -> c 其中p数组存储的是从p[p[i]] 到 p[i] 的最长递增子序列索引，也就是前一个b的索引； r数组存储最后一个元素也就是c的索引 */