第十九天(树)

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

• 两层以内的树单独计算

• 两层以上的树需要按每层考虑(BFS)

  • 同一层内的结点的子树情形对称(每个结点有四种情形)

  • 同一层内的结点的数值对称

1611,110:平衡二叉树

• 定义:任意节点的左右子树的深度相差不超过1

• 为每个结点生成其左右子树的高度

  • 若无则为0

  • 若有则为子树递归遍历的结果+1

  • 返回左右子树较大的高度,即为当前子树的高度.

• 在生成高度期间,判断有无高度之差绝对值超过1的

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

• 左子树的最右边=较小值中的最大值

• 右子树的最左边=较大值中的最小值

• 从而可以找到这个结点与其他所有结点的最小差的绝对值

• 再取所有绝对差中的最小值

653:两数之和

• 遍历树(后序和BFS较好)

  • 判断(目标数-当前结点数)是否在set中

  • 不在则添加当前结点树到set中

  • 在则返回确定结果

• set用来查找一个数的存在,效果是O(1)