# 第十九天(树)

**今天完成题目**:1580,1611,110,530,653\
1580:对称的二叉树

* 两层以内的树单独计算
* 两层以上的树需要按每层考虑(BFS)
  * 同一层内的结点的子树情形对称(每个结点有四种情形)
  * 同一层内的结点的数值对称

1611,110:平衡二叉树

* 定义:任意节点的左右子树的深度相差不超过1
* 为每个结点生成其左右子树的高度
  * 若无则为0
  * 若有则为子树递归遍历的结果+1
  * 返回左右子树较大的高度,即为当前子树的高度.
* 在生成高度期间,判断有无高度之差绝对值超过1的

530:二叉搜索树的最小绝对差:

* 左子树的最右边=较小值中的最大值
* 右子树的最左边=较大值中的最小值
* 从而可以找到这个结点与其他所有结点的最小差的绝对值
* 再取所有绝对差中的最小值

653:两数之和

* 遍历树(后序和BFS较好)
  * 判断(目标数-当前结点数)是否在set中
  * 不在则添加当前结点树到set中
  * 在则返回确定结果
* set用来查找一个数的存在,效果是O(1)
