第二十一天(树)

今天完成题目: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列入候选结果,选择最大值.