数据结构 — 树专题

将会用几天的时间完成全部内容的整理

专题涉及树的基本内容 树，二叉树，二叉搜索树。
包含下列题中的一部分

一般而言，给出的树 一般都是无向的，因此邻接表存储的时候，要注意存储无向边。
1. 树的存储与遍历
一般的树，通常多叉。因此，可以看成稀疏图。存储采用邻接矩阵，遍历用BFS或DFS
1478 统计叶子节点
2. 树的直径
利用树形DP 求解带负权边的树的直径。
任意选择一个点作为根节点，利用dfs找到它的所有子节点到叶节点的最大路径和次大路径，两者相加就是树的直径。
1072 树的最长路径
树的中心，找到树中到最远的点的距离最小。可以看做对1072的扩展，利用两个dfs分别求出当前点cur 来自子节点的最大路径与来自父节点的最大路径。属于模板题，推荐直接背过。
1073 树的中心
连通块判断 + 树的直径 (两个模板 拼成一道题)
1500 最深的根
3.二叉树的前序 中序 后序遍历序列
利用中序和(前序或后序)序列 构造树。
利用中序遍历 前序遍历 后序遍历性质。
1497 树的遍历
只利用二叉树的前序遍历序列构建树
目前没有整理好静态二叉链表的模板 只有动态写法
3384 二叉树遍历
4.二叉搜索树
1589 构建二叉搜索树