IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 剑指offer-55-I:二叉树的深度(后序遍历 |层序遍历) -> 正文阅读

[数据结构与算法]剑指offer-55-I:二叉树的深度(后序遍历 |层序遍历)

树的遍历方式总体分为两类:深度优先搜索(DFS)、广度优先搜索(BFS);

  • 常见的 DFS : 先序遍历、中序遍历、后序遍历;
  • 常见的 BFS : 层序遍历(即按层遍历)。

求树的深度需要遍历树的所有节点,本文将介绍基于 后序遍历(DFS) 和 层序遍历(BFS) 的两种解法。

方法一:

后序遍历(DFS)

  • 树的后序遍历 / 深度优先搜索往往利用 递归 或 栈 实现,本文使用递归实现。
  • 关键点: 此树的深度和其左(右)子树的深度之间的关系。显然,此树的深度 等于 左子树的深度 与 右子树的深度 中的 最大值 +1 。

算法解析:

  • 终止条件: 当 root? 为空,说明已越过叶节点,因此返回 深度 0 。
  • 递推工作: 本质上是对树做后序遍历。
    • 计算节点 root? 的 左子树的深度 ,即调用 maxDepth(root.left);
    • 计算节点 root? 的 右子树的深度 ,即调用 maxDepth(root.right);
  • 返回值: 返回 此树的深度 ,即 max(maxDepth(root.left), maxDepth(root.right)) + 1。

复杂度分析:

  • 时间复杂度 O(N) : N 为树的节点数量,计算树的深度需要遍历所有节点。
  • 空间复杂度 O(N): 最差情况下(当树退化为链表时),递归深度可达到 N 。

代码:

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root: return 0
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

方法二

层序遍历(BFS)

  • 树的层序遍历 / 广度优先搜索往往利用 队列 实现。
  • 关键点: 每遍历一层,则计数器 +1 ,直到遍历完成,则可得到树的深度。

算法解析:

  • 特例处理: 当 root? 为空,直接返回 深度 00 。
  • 初始化: 队列 queue (加入根节点 root ),计数器 res = 0。
  • 循环遍历: 当 queue 为空时跳出。
    初始化一个空列表 tmp ,用于临时存储下一层节点;
    • 遍历队列: 遍历 queue 中的各节点 node ,并将其左子节点和右子节点加入 tmp;
    • 更新队列: 执行 queue = tmp ,将下一层节点赋值给 queue;
    • 统计层数: 执行 res += 1 ,代表层数加 1;
  • 返回值: 返回 res 即可。

复杂度分析

  • 时间复杂度 O(N) : N 为树的节点数量,计算树的深度需要遍历所有节点。
  • 空间复杂度 O(N): 最差情况下(当树平衡时),队列 queue 同时存储 N/2 个节点。

代码

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root: return 0
        queue, res = [root], 0
        while queue:
            tmp = []
            for node in queue:
                if node.left: tmp.append(node.left)
                if node.right: tmp.append(node.right)
            queue = tmp
            res += 1
        return res

作者:jyd
链接:https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/solution/mian-shi-ti-55-i-er-cha-shu-de-shen-du-xian-xu-bia/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-07-17 12:12:08  更:2021-07-17 12:12:27 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/25 16:33:10-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码