由遍历序列构造出二叉树 仅知道一种遍历序列是无法确定唯一的二叉树的，以中序遍历为例，对于一个中序遍历序列“BDCAE”，其对应的树形结构可能有下面三种：
因此，至少需要两种遍历序列才可以推知树形结构。
1.前序+中序遍历序列 🎈基本步骤 由前序遍历的特性得知，前序遍历中第一个节点必然为根节点，因此根据中序遍历特性，根节点左边为左子树下的所有节点，右边为右子树下的所有节点，然后分别在左子树序列右子树序列中重复进行即可。
🎈示例
前序遍历序列：A D B C E 中序遍历序列：B D C A E 首先能确定根节点为A，根据中序遍历序列可以得到：
对于左子树BDC，根据前序遍历，此子树根节点为D，根据中序遍历序列：
至此，二叉树的还原工作就完成了！至于更复杂的序列，逐步推断即可😋
2.后序+中序遍历序列 🔑与1不用的是，后序遍历中根节点为后序遍历序列尾部的那个节点，其余参照1即可！
3.层序遍历+中序遍历 🔑 根据层序遍历特性，层序遍历中根节点始终在子树前面，“根左右”
🎈示例
层序遍历序列：A D E B C 中序遍历序列：B D C A E 根节点为A，根据中序遍历序列可以得到：
对于左子树BDC，根据前序遍历，此子树根节点为D，根据中序遍历序列：
思考 如果前序，后续，层序两两组合能否确定唯一的树结构？
假设给定序列如下：
前序：A B 后序：B A 层序：A B 其两两组合都满足两种结构：
因此前序，后续，层序两两组合不能确定唯一的树结构。
向量的空间管理，有静态和动态两种策略
静态空间管理策略 开辟内部数组_elem[]并使用一段地址连续的物理空间，_capacity表示总容量 ，_size表示当前的实际规模n，示意图如下：
若采用静态空间管理策略，容量_capacity固定，则有明显的不足…
上溢/overflow： _elem[]不足以存放所有元素，尽管此时系统往往仍有足够的空间
下溢/underflow： _elem[]中的元素寥寥无几，装填因子 λ = _size / _capacity « 50%
动态空间管理策略 在即将上溢时，适当扩大内部数组的容量
递增策略 当需要扩容时，为_capacity追加固定大小的空间，即
T* oldElem = _elem; _elem = new T[ _capacity += INCREMENT ]; 考虑最坏情况，在初始容量为0的空向量中连续插入n = m*I个元素
那么，在第1，I+1，2I+1，3I+1…次插入元素时都需要扩容，表示为
倍增策略 当需要扩容时，增加_capacity 为原来的两倍，即
T* oldElem = _elem; _elem = new T[ _capacity <<= 1 ]; 考虑最坏情况，在初始容量为1的空向量中连续插入n = 2^m个元素
那么，在第1，2，4，8…次插入元素时都需要扩容，表示为
两种策略的复杂度分析 考虑最坏的情况，两种策略的复杂度分别为
递增策略： 为算术级数，0+I+2I+…=O(n ²) 倍增策略： 为几何级数，1+2¹+2²+2³+…=O(2^m)=O(n) 递增策略 倍增策略 累计时间 O(n ²) O(n) 分摊时间 O(n) O(1) 装填因子 λ ≈100% >50% 可以看出，倍增策略在牺牲空间的基础上，换取时间上的巨大提升，可采取√...
减而治之(Decrease and conquer) 什么是“减而治之”？
为求解一个大规模的问题，可以将其划分为两个问题，其一平凡，另一规模缩减 ，分别求解子问题，由子问题的解得原问题的解
比如说，对于一个数组A的求和问题，可以设计如下的算法
sum( int A[], int n ) { return n < 1? 0 : sum(A, n - 1) + A[n - 1]; } 当规模缩减到一定程度后，抵达递归基，返回0
复杂度分析 1. 递归跟踪
绘出计算过程中出现过的所有递归实例（及其调用关系） ，那么它们各自所需时间之总和，即为整体运行时间
上例中，共计n+1个递归实例(分析)，各自只需O(1)时间 故总体运行时间为：
T(n) =O(1) × (n+1) =O(n)
2.递推方程
对于大规模的问题、复杂的递归算法，递归跟踪不再适用 此时可采用另一抽象的方法…
在本例中，有T(n)=T(n-1) + O(1),T(0)=O(1)
则，T(n) = T(n-2)+O(2) = T(n-3)+O(3) = T(n-n)+O(n)=O(n)
可以看到，两种分析方法的出来复杂度都为O(n)
分而治之(Divide and conquer) 什么是“分而治之”？...
导论 所谓算法，即特定计算模型下，旨在解决特定问题的指令序列。输入：待处理的信息（问题）输出：经处理的信息（答案）
正确性 的确可以解决指定的问题
确定性 任一算法都可以描述为一个由基本操作组成的序列
可行性 每一基本操作都可实现，且在常数时间内完成
有穷性 对于任何输入，经有穷次基本操作，都可以得到输出
::: tip Algorithms + Data Structures = Programs
(Algorithms + Data Structures) x Efficiency = Computation
:::
如何评判算法的其优劣(计算模型) 实验统计是最直接的方法，但足以准确反映算法的真正效率？不足够！ - 不同的算法，可能更适应于不同规模的输入 - 不同的算法，可能更适应于不同类型的输入 - 同一算法，可能由不同程序员、用不同程序语言、经不同编译器生成 - 同一算法，可能实现并运行于不同的体系结构、操作系统… 为给出客观的评判，需要抽象出一个理想的平台或模型 - 不再依赖于上述种种具体的因素 - 从而直接而准确地描述、测量并评价算法
1.图灵机模型(TM)
组成 说明 Tape 依次均匀地划分为单元格 各存有某一字符，初始均为'#' Head 总是对准某一单元格，并可 读取或改写其中的字符。每经过一个节拍，可 转向左侧或右侧的邻格 Alphabet 字符的种类有限 State TM总是处于有限种状态中的某一种 。每经过一个节拍 可按照规则转向另一种状态 。统一约定，‘h’ = halt(停止) 2....