【力扣】104. 二叉树的最大深度(DFS、BFS)
2022/1/22 23:08:54
本文主要是介绍【力扣】104. 二叉树的最大深度(DFS、BFS),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目:
104. 二叉树的最大深度 给定一个二叉树,找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 说明: 叶子节点是指没有子节点的节点。 示例: 给定二叉树 [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回它的最大深度 3 。
方法一:深度优先搜索
思路:
如果我们知道左子树和右子树的最大深度a和b,那么该二叉树的最大深度即为max(a,b)+1
而左子树和右子树的最大深度又可以以同样的方式进行计算。因此,我们可以用【深度优先搜索】的方法来计算二叉树的最大深度。具体来说,在计算当前二叉树的最大深度时,可以先递归计算出其左子树和右子树的最大深度,然后在O(1)时间内计算出当前二叉树的最大深度。递归在访问到空节点时退出。
代码:
class Solution { public int maxDepth(TreeNode root) { if(root==null){ return 0; } return Math.max(maxDepth(root.right),maxDepth(root.left))+1; } }
复杂度分析:
- 时间复杂度:O(n),其中n为二叉树节点的个数。每个节点在递归中只被遍历一次。
- 空间复杂度:O(height),其中height表示二叉树的高度。递归函数需要栈空间,而栈空间取决于递归的深度,因此空间复杂度等价于二叉树的深度。
方法二:广度优先搜索
思路:
- 准备队列
- 根节点入队列
- 队头出队列,并对出队列的元素的左右子节点入队列。
- 当前这一层的出完队列后再对下一层的继续
- 即通过一个while循环从上向下一层层遍历,for遍历控制每一层从左向右遍历。
代码:
// 广度优先搜索 class Solution { public int maxDepth(TreeNode root) { if(root == null){ return 0; } int ans = 0; Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.add(root); while(!queue.isEmpty()){ int size = queue.size(); for(int i = 0; i < size ;i++ ){ // 队头出队列 TreeNode node = queue.remove(); if(node.left != null){ queue.add(node.left); } if(node.right != null){ queue.add(node.right); } } ans++; } return ans; } }
复杂度分析:
- 时间复杂度:O(n),其中n为二叉树的节点个数,树的每个节点都要被访问一次。
- 空间复杂度:此方法空间的消耗取决于队列存储的元素数量,其在最坏情况下会达到O(n)。
这篇关于【力扣】104. 二叉树的最大深度(DFS、BFS)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm,再安排pandas等模块,说是没有打包工具?
- 2024-05-29java11新特性
- 2024-05-29哪些无用敏捷指标正在破坏敏捷转型?
- 2024-05-29鸿蒙原生应用再新丁!新华社 入局鸿蒙
- 2024-05-29设计模式 之 迭代器模式(Iterator)