代码随想录算法训练营二刷第9天 | 二叉树的节点数量、二叉树的平衡和二叉树的所有路径

完全二叉树的节点个数

方法一:递归法——后序遍历;层序遍历,这是普通的二叉树求节点的方法!

方法二: 要注意到,完全二叉树中是包含了满二叉树的,(在完全二叉树中如何判断子树是满二叉树呢?方法为:(在完全二叉树中,向左递归的深度 = 向右递归的深度))。那么用后序遍历的方法求完全二叉树的节点数量,首先应该判断一个子树是否是满二叉树,并计算该满二叉树的深度,若是,直接用公式计算该子树的节点数量,若不是则继续递归。

平衡二叉树

深度优先遍历递归法,处理的内容就是,分别计算节点的左右子树的高度,判断左右子树的高度差绝对值超不超过1(求高度用的是后序遍历),若不超过1,则返回该节点的最大高度;若超过1,那就不用再进行判断了,因为整颗树就已经是非平衡的二叉树,直接返回false就可以了!

二叉树的所有路径

1、很明显,采用前序遍历!

2、本题涉及到了回溯,要注意:回溯和递归是一一对应的,有一个递归,就要有一个回溯,在 递归函数中 往往已经对某个节点进行了处理,因此,在递归函数中 再嵌套调用递归函数后,相当于已经处理了下一个节点,所以在调用完递归函数后,进行回溯!

相关推荐

最近更新

  1. TCP协议是安全的吗?

    2024-05-04 13:04:01       18 阅读
  2. 阿里云服务器执行yum,一直下载docker-ce-stable失败

    2024-05-04 13:04:01       18 阅读
  3. 【Python教程】压缩PDF文件大小

    2024-05-04 13:04:01       17 阅读
  4. 通过文章id递归查询所有评论(xml)

    2024-05-04 13:04:01       20 阅读

热门阅读

  1. 综合案例(账号密码登录和SQL注入)

    2024-05-04 13:04:01       11 阅读
  2. 我的创作纪念日

    2024-05-04 13:04:01       10 阅读
  3. 批处理任务的通用工具类

    2024-05-04 13:04:01       9 阅读
  4. git简介

    git简介

    2024-05-04 13:04:01      9 阅读
  5. 【Trick】conda指令安装yml文件中的python依赖

    2024-05-04 13:04:01       11 阅读
  6. 纯正英语新闻 5.7(提前)

    2024-05-04 13:04:01       9 阅读
  7. CDA Level Ⅰ 2023认证考试大纲

    2024-05-04 13:04:01       16 阅读
  8. Flask知识点汇总表格总结

    2024-05-04 13:04:01       9 阅读
  9. c++ memset 指针示例

    2024-05-04 13:04:01       9 阅读
  10. Element-UI库:Web前端开发的强大助力

    2024-05-04 13:04:01       14 阅读