1. 1. 树
a. 二叉树中是否存在和为指定值的路径
i. 递归，子树是否存在指定值-root.value的子树，叶节点返回结果
ii. 层序遍历，借助queue, 节点值改为从上到下累加值，叶节点判断是否等于sum
b. 二叉树中和为指定值的路径有哪些
i. 递归函数多加一个参数list存储结果，返回类型为void
1. 1. 递归判断子树是否存在原指定值-root.value的子路径
2. 2. 如果叶节点满足要求，加入list
ii. 层序遍历，借助queue, 节点值改为从上到下累加值，叶节点判断是否等于sum
c. 二叉树根节点到叶节点的所有路径的和
i. 先bfs或dfs，递归非递归均可，求出所有的叶节点的路径
1. 1. 可以借助队列bfs，改变val,最后一层就是叶节点的路径
2. 2. 可以构造递归，三个参数，结果list, 当前路径，当前根节点
a. 当为叶节点时，将结果加入list
b. 当不为页节点，补充当前路径
ii. 求路径之和
d. 找到搜索二叉树中两个错误的节点
i. 中根遍历，存到数组中
ii. 遍历数组，从左到右找到第一个大于下一个的节点n1，从右往左做到的一个小于左边的节点n2，n2 n1即为所求
iii. 时间复杂度n，空间复杂度n
e. 二叉树中两个节点的最近公共祖先
i. 分别求跟节点到这两个节点的路径
1. 1. 构造递归函数，传入root, stack, key, 返回boolean
2. 2. 如果遍历儿子节点返回true，将当前位置压栈
ii. 对于路径，求最长前缀, 两边同时从各自栈中弹出元素至不等为止
f. 前序遍历和中序遍历，重建二叉树
i. 递归
ii. 切分数组，递归左子树，递归右子树
iii. 时间复杂度n
g. 根据前序遍历，中序遍历恢复二叉树，并打印二叉树的最右视图
i. 递归，切分数组，递归左子树，递归右子树
ii. 层序遍历恢复好的二叉树，将每一层的最后一个元素存入list
h. 判断二叉树是否为搜算二叉树和完全二叉树
i. 判断搜索二叉树
1. 1. 递归，当前是不是，如果是，左右子树分别是不是
2. 2. Bfs，借助队列实现
ii. 判断完全二叉树
1. 1. Bfs, 如果当前节点不存子节点，那么从当前节点开始，任何节点都是叶子节点，如果满足返回true
i. 树的直径，树中两个距离最远的叶节点之间的距离(图的查询)
i. 点个数，边集合，边权重
ii. 先找距离根节点最远的点，从该点出发，寻找图中距离该点的最远点
iii. 通过邻接表构建图，HashMap>
iv. 构建递归方法进行图中某一个点到另一个点的最长路径搜索方法
1. 1. 参数
a. 图
b. 从哪个节点开始
c. 上一个节点
d. 之前的路径和
e. 当前最大的值和位置，外部定义，传入引用
2. 2. 返回值 void
j. 完全二叉树的节点数
i. 方法一，递归，左+右，和是否完全二叉树没关系
1. 1. 时间复杂度n
ii. 方法二，二分查找，构造递归
1. 1. 要么左边为满二叉树，要么右子树为满二叉树，每次可以砍掉一半
2. 2. 如果左子树高度==右子树高度，说明左子树满
a. Return Math.power(2,LH)-1+1+递归右子树的节点数
3. 3. 如果左子树高度>右子树高度，说明右子树满
a. Return Math.power(2,RH)-1+1+ 递归左子树的节点数
4. 4. 还需要构造求树高的函数
5. 5. 时间复杂度为2logn
k. 二叉搜索树与双向链表
i. 递归，返回左子树的最左节点为链表的头
ii. 如果左子树非空，root.left= fun(左子树)，root.right=fun(右子树)
iii. 找到左子树的最右节点，最右节点.right=root
iv. 右子树的头结点.left=root
l. 判断二叉树是否对称
i. 递归
1. 1. 左子节点是否等于右子节点，如果等于，判断左子树的左子树是否等于右子树的右子树，判断右子树的左子树是否等于左子树的右子树
ii. 层序遍历
1. 1. 判断每层是否对称
2. 2. 时间复杂度n，空间复杂度n
m. 二叉树的最大深度
i. 递归，左右深度的max+1
ii. 层序遍历，用到queue
n. 是否平衡二叉树
i. 递归，返回树高，如果不平衡，返回-1
ii. 左子树是否平衡，右子树是否平衡，返回树高
o. 二叉搜索树的第K个节点
i. 中根遍历二叉树，遍历的结果存储在全局List中
ii. 当List的长度大于k，返回
iii. 时间复杂度n，空间复杂度k
p. 合并两个二叉树的值
i. 递归，合并root的值，分别合并左子树，右子树
q. T1树中是否有与T2拓扑结构完全相同的子树
i. 方法1，层序遍历+递归
1. 1. 层序遍历T1，T1的每个节点作为根与T2节点比对是否拓扑结构相同
2. 2. 时间复杂度n^2
ii. 方法2，分别进行中根遍历，保存结果到字符串st1,st2
1. 1. 字符串可以为val_val_val这样的形式，判断st2是否是st1的字串
2. 2. 时间复杂度n^2
r. 有序数组转换为平衡二叉树
i. 递归构建树，寻找root节点，数组分为两半
ii. root.left=构建左子树，root.right=构建右子树
iii. 时间复杂度n
s. 二叉树的先序，中序，后续遍历
i. 递归，传入List, 注意先中后指的是根节点的先中后
t. 二叉树的层序遍历
i. 构造queue，for循环，每次遍历一层，将子节点入队
u. 二叉树之字形层序遍历
i. 与层序遍历的区别是构造方向，每遍历一层改变方向
v. 把二叉树打印成多行
i. Bfs, 借助队列层序遍历
w. 二叉树的镜像
i. 递归，左子树等于递归右子树，右子树等于递归左子树
ii. 时间复杂度n, 空间复杂度n
x.
