qq在线网站代码,营销策划书范文,番禺网站建设,建筑资源网站目录 问题描述
示例
示例 1#xff1a;
示例 2#xff1a;
约束条件
题解
方法一#xff1a;广度优先搜索#xff08;BFS#xff09;
步骤
代码实现
方法二#xff1a;递归
步骤
代码实现
结论 问题描述
给定一个二叉树 root#xff0c;我们需要返回其最大…目录 问题描述
示例
示例 1
示例 2
约束条件
题解
方法一广度优先搜索BFS
步骤
代码实现
方法二递归
步骤
代码实现
结论 问题描述
给定一个二叉树 root我们需要返回其最大深度。二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。
示例
示例 1
输入root [3,9,20,null,null,15,7] 输出3
示例 2
输入root [1,null,2] 输出2
约束条件
树中节点的数量在 [0, 10^4] 区间内。-100 Node.val 100
题解
我们将使用两种方法来解决这个问题广度优先搜索BFS和递归。
过题图片 方法一广度优先搜索BFS
BFS 是一种遍历树的层序方法它从根节点开始逐层遍历树的每个节点。在每一层我们记录节点的数量直到遍历完所有节点。
步骤
如果根节点为空返回深度为 0。初始化一个队列将根节点加入队列。初始化一个计数器用于记录当前层的深度。当队列不为空时执行以下操作 记录当前层的节点数。遍历当前层的每个节点将它们的子节点加入队列并更新深度计数器。返回深度计数器的值。
代码实现 java
import java.util.LinkedList;
import java.util.Queue;class Solution {public int maxDepth(TreeNode root) {if (root null) return 0;QueueTreeNode queue new LinkedList();queue.offer(root);int depth 0;while (!queue.isEmpty()) {int size queue.size();for (int i 0; i size; i) {TreeNode node queue.poll();if (node.left ! null) queue.offer(node.left);if (node.right ! null) queue.offer(node.right);}depth;}return depth;}
}
方法二递归
递归方法利用了二叉树的最大深度属性一个节点的最大深度是其左子树和右子树最大深度的最大值加 1。
步骤
如果根节点为空返回深度为 0。递归计算左子树和右子树的最大深度。返回左子树和右子树最大深度的最大值加 1。
代码实现 java复制
class Solution {public int maxDepth(TreeNode root) {if (root null) return 0;return 1 Math.max(maxDepth(root.left), maxDepth(root.right));}
}
题目链接
104. 二叉树的最大深度 - 力扣LeetCode
结论
两种方法都可以有效地求解二叉树的最大深度问题。BFS 方法在遍历过程中逐层计算深度而递归方法利用了树的结构特性进行求解。根据具体的应用场景和偏好可以选择适合的方法。
