# 第二十一天(树)

**今天完成题目**:543,112,572,671,501,111,687\
543:二叉树的直径

* 直径等于左右子树的最大深度之和
* 在dfs时候用left和right记录左右子树的最大深度

112:路径总和

* 在遍历时候,目标总和不断减去遍历结点的值
* 直到根结点等于目标总和剩余的值,说明存在

572:另一个树的子树

* 暴力法:遍历所有结点,并逐个判断该结点是否为目标树
* 套路法:引入两个空值 lNull 和 rNull，当一个节点的左孩子或者右孩子为空的时候，就插入这两个空值，这样 DFS 序列就唯一对应一棵树。
  * 通过dfs获得当前树的序列和目标树的序列
  * 通过KMP算法判断目标树的序列是否为当前树的子序列
  * KMP算法(什么时候背一下?):利用最大公共前后缀避免回溯

671:二叉树中第二小的结点

* 该树特性:子节点为0或2,且父结点等于子结点中较小的一个==>根值最小
* 若有子结点进递归,若左子结点等于根,则往该方向递归,并将其兄弟结点列入候选.
* 从所有候选中选择较小的结点,且不等于根结点,就是第二小的.

501:二叉搜索树中的众数

* 暴力法:遍历并建立字典,而后按值排序,前面若干个值相等的键为众数
* 节省空间法:先中序遍历确定结果集的大小(众数的数量)和达到多少是众数,再申请空间后,再中序遍历将符合数量的数作为众数

111:二叉树的最小深度

* 遍历到叶子结点并同时计算出此时深度,选择所有深度中最小的.

687:最长同值路径

* 设置一个preVal记录父结点的值
* 设置left和righ记录左右子树的最长同值路径(不绕弯的)
* 如果当前结点的值等于preVal,则返回max(left,right)+1
* 在每个非叶子结点,将left+right列入候选结果,选择最大值.
