吾日三省吾身
还记得的梦想吗
正在努力实现它吗
可以坚持下去吗
目录
力扣题号：104. 二叉树的最大深度 - 力扣（LeetCode）
| (╯°□°）╯︵ ┻━┻ | (⌐■_■) |
| (¬‿¬) | (´･ω･`) |
| ( ͡° ͜ʖ ͡°) | (づ￣ ³￣)づ |
力扣题号：104. 二叉树的最大深度 - 力扣（LeetCode）
注：下述题目描述和示例均来自力扣
题目描述：
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：3
示例 2：
输入：root = [1,null,2] 输出：2
提示：
- 树中节点的数量在
[0, 104]区间内。 -100 <= Node.val <= 100
思路
解法一：递归
实现思路
-
递归计算深度： 通过递归的方式，计算每个节点的左右子树的深度，然后选择较大的那个作为当前节点的深度。
-
递归终止条件： 当节点为空时，返回深度0。
-
递归返回： 将每个节点的左右子树的深度进行比较，并加上当前节点，得到当前节点的深度。
代码逻辑解释
- 使用递归方式计算每个节点的深度，每次递归都会比较左右子树的深度，并选择较大的那个作为当前节点的深度。
- 递归终止条件为节点为空，此时返回深度0。
- 在递归返回时，选择左右子树的深度中的较大值，并加上1，即可得到当前节点的深度。
注意事项
- 通过递归计算每个节点的深度，遍历整棵树，并选择最大的深度作为结果。
- 使用了递归的方式，简化了代码的实现，并且符合二叉树的特性。
代码实现
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
// 计算二叉树的最大深度
public int maxDepth(TreeNode root) {
// 调用递归方法，获取最大深度
int max = chooseMax(root);
return max;
}
// 辅助方法，递归计算节点的最大深度
public int chooseMax(TreeNode node){
// 递归终止条件：节点为空，深度为0
if (node == null){
return 0;
}
// 递归计算左右子树的深度
int leftMax = chooseMax(node.left);
int rightMax = chooseMax(node.right);
// 当前节点的深度为左右子树中的较大深度加1
int depth = Math.max(leftMax, rightMax) + 1;
return depth;
}
}
内存优化
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
// 计算二叉树的最大深度
public int maxDepth(TreeNode root) {
// 调用递归方法，获取最大深度
return chooseMax(root);
}
// 辅助方法，递归计算节点的最大深度
public int chooseMax(TreeNode node){
// 递归终止条件：节点为空，深度为0
if (node == null){
return 0;
}
// 递归计算左右子树的深度
// 当前节点的深度为左右子树中的较大深度加1
return Math.max(chooseMax(node.left), chooseMax(node.right)) + 1;
}
}
总结
不总结了，谢谢各位，累了
标签：TreeNode,递归,val,int,二叉树,深度,第六章,节点 From： https://blog.csdn.net/DDDDWJDDDD/article/details/136720571