Python入门到实战 ruby Material UI 建造师报考条件 matlab停止运行命令 打印缩放怎么设置 matlab注释一段 oracle连接字符串 mysql卸载工具 python面向对象 python返回函数 java编程 java数据库 java基本语法 java开发教程 java学习文档 java连接sql数据库 java类方法 linux教程 python网站开发实例 凯立德地图免费下载 linux命令详解词典 计算机操作系统第四版 kms神龙 java游戏编程 网络文件服务器 ansys安装教程 不屑表情包 电脑代码雨 一键换肤大师 网页自动点击 oledbconnection linux系统下载 cad2008汉化包 抖音APP下载 打印机怎么打印照片 js文件上传插件 ps怎么羽化图片边缘 x截屏 cad代理信息
当前位置: 首页 > 学习教程  > python

剑指 Offer 55 - I. 二叉树的深度(DFS和BFS)

2021/2/6 22:26:41 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

难度:简单 输入一棵二叉树的根节点,求该树的深度。从根节点到叶节点依次经过的节点(含根、叶节点)形成树的一条路径,最长路径的长度为树的深度。 例如: 给定二叉树 [3,9,20,null,null,15,7], 返…

难度:简单

输入一棵二叉树的根节点,求该树的深度。从根节点到叶节点依次经过的节点(含根、叶节点)形成树的一条路径,最长路径的长度为树的深度。

例如:

给定二叉树 [3,9,20,null,null,15,7],
树
返回它的最大深度 3 。

解题思路:
这种题目无非就是遍历树,遍历的方法有两种——深度优先搜索(DFS)和广度优先搜索(BFS)。

DFS:
DFS需要注意的是每次递归返回的时候需要比较左子树和右子树的最大深度,而不是加和,不然会计算重复。
BFS:
BFS没有需要特别注意的,就是传统利用队列遍历,关注队列是否为空,然后每遍历一层队列,就加入下一层。

python代码:

# DFS
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        return self.deSearch(root)
    def deSearch(self, root):
        if not root:
            return 0
        l_depth = self.deSearch(root.left)
        r_depth = self.deSearch(root.right)
        max_depth = max(l_depth, r_depth)
        return max_depth+1

复杂度分析:

  • 时间复杂度 O ( N ) O(N) O(N) N N N是节点的数目,我们需要遍历所有节点;
  • 空间复杂度 O ( N ) O(N) O(N):这里只能讨论最差的情况,最差的情况是这棵树是一个链表,递归的深度为 N N N
# BFS
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        return self.brSearch(root)
    def brSearch(self, root):
        if not root: return 0
        depth = 0
        queue = [root]
        while queue:
            tmp = []
            for node in queue:
                if node.left: tmp.append(node.left)
                if node.right: tmp.append(node.right)
            queue = tmp
            depth += 1
        return depth

复杂度分析:

  • 时间复杂度 O ( N ) O(N) O(N) N N N是节点的数目,跟DFS一样,我们需要遍历所有节点;
  • 空间复杂度 O ( N ) O(N) O(N):这里也是最差的情况,当树是完全二叉树的情况下,队列需要同时存储 N / 2 + 1 N/2+1 N/2+1

本文链接: http://www.dtmao.cc/news_show_2000105.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?