第十八天(树)

今天完成题目:107,1022,637,235,257,872,538,1723,100 107:二叉树的层次遍历

• 通过队列完成二叉树的层次遍历

• 每一层需要一个临时队列存储该层数据

1022:从根到叶的二进制数之和

• 使用深度遍历完成,并且每进入下一层,数字需要左移一位,并加上当前结点的值

• ^在python是异或,**才是指数

637:二叉树的层平均值

• 类似107实现层遍历而后计算平均值

235:二叉搜索树的最近公共祖先

• 昨天做过,判断p,q所在的位置即可,分为三种情况

  • p,q均在右子树中,递归查找右子树

  • p,q均在左子树中,递归查找左子树

  • p,q已经找到其中一个,或者p,q分别在左右子树中,则返回当前结点作为答案.

257:二叉树的所有路径

• 通过深度遍历输出所有路径

872:叶子相似的树

• 保存所有叶子结点

• 通过==符号可以判断两个叶子list是否完全相同

538:把二叉搜索树转换为累加树

• 按照右中左的逆中序遍历,从而获得从大到小的值

• 记录累加值,并将当前结点改为该值

1723:BiNode

• 把二叉搜索树转换为单向链表，要求依然符合二叉搜索树的性质，转换操作应是原址的

• 设置一个结点pre记录上一个结点

• 按照左中右的中序遍历,获得从小到大的值

  • 当前节点的左节点置空

  • 将当前节点置为上一结点的右节点

  • 更新pre结点为当前结点

100:相同的树

• 设置默认回答为True(全局变量,也可以用来中止递归)

• 遍历二叉树,当发现某一个情况为错误时,设置回答为错

  • 其中一颗树的左结点存在而右结点不存在

  • 其中一颗树的右结点存在而左结点不存在

  • 一棵树的当前结点都存在,但值不等

  • 其他情况继续递归