34二叉树-BFS和DFS求树的深度
目录
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;Queue<TreeNode> 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来找到所有路径，然后选择其中最短的路径。综合考虑问题的需求和数据结构的特点，选择适当的算法。