接网站开发项目,南京小程序建设,柳州学校网站建设,WordPress购物个人中心目录
LeetCode之路——104. 二叉树的最大深度
分析
解法一#xff1a;广度优先遍历
解法二#xff1a;深度优先遍历
总结
深度优先搜索 (DFS)
广度优先搜索 (BFS LeetCode之路——104. 二叉树的最大深度
给定一个二叉树 root #xff0c;返回其最大深度。
二叉树的…目录
LeetCode之路——104. 二叉树的最大深度
分析
解法一广度优先遍历
解法二深度优先遍历
总结
深度优先搜索 (DFS)
广度优先搜索 (BFS LeetCode之路——104. 二叉树的最大深度
给定一个二叉树 root 返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 示例 1 输入root [3,9,20,null,null,15,7]
输出3
示例 2
输入root [1,null,2]
输出2 提示 树中节点的数量在 [0, 104] 区间内。 -100 Node.val 100 分析
解法一广度优先遍历
class Solution {public int maxDepth(TreeNode root) {if(root null) return 0;QueueTreeNode queue new LinkedList();
queue.offer(root);int deep 0;while(!queue.isEmpty()){int len queue.size();while(len 0){TreeNode curr queue.poll();if(curr.left ! null) queue.offer(curr.left);if(curr.right ! null) queue.offer(curr.right);len--;}deep;}return deep;}
} 时间复杂度O(n) 空间复杂度O(n)
解法二深度优先遍历
class Solution {public int maxDepth(TreeNode root) {if(root null) {return 0;} else {int leftDeep maxDepth(root.left);int rightDeep maxDepth(root.right);return Math.max(leftDeep, rightDeep) 1;} }
} 时间复杂度O(n) 空间复杂度O(deep) 总结
深度优先搜索 (DFS) 遍历顺序以深度为优先从根节点开始沿着一条路径尽可能深入然后回溯并继续深入到下一个分支。 数据结构通常使用递归或显式的栈数据结构来实现。递归调用构成了一个栈用于跟踪路径。 适用性适用于寻找路径、拓扑排序、连通性分析、深度分析等问题。通常用于在图中找到一条路径或寻找目标节点。 空间复杂度通常具有较低的空间复杂度尤其在递归版本中。但在非平衡树中空间复杂度可能较高。 实现难度通常更容易实现特别是使用递归。递归版本的DFS代码通常较短。
广度优先搜索 (BFS 遍历顺序以广度为优先从起始节点开始首先访问所有与起始节点直接相邻的节点然后逐层向外扩展依次访问更远的节点。 数据结构通常使用队列数据结构来实现。队列用于存储待访问的节点确保先访问当前层的节点然后再访访问下一层的节点。 适用性适用于寻找最短路径、最短距离、广度分析等问题。通常用于寻找最短路径或在树/图中查找目标节点。 空间复杂度通常具有较高的空间复杂度因为它需要存储待访问节点的队列。在完全图中空间复杂度可能最高。 实现难度相对较复杂需要维护一个队列处理节点的层级等。
选择DFS还是BFS取决于问题的性质。如果要找到最短路径BFS通常更合适。如果要执行深度分析或寻找路径DFS可能更适合。在某些情况下它们可以相互转化为其他问题例如可以使用DFS来找到所有路径然后选择其中最短的路径。综合考虑问题的需求和数据结构的特点选择适当的算法。
