一、知识点:
递归、二叉树
二、文字分析:
使用了递归的方式来计算二叉树的最大深度。首先判断根节点是否为空,如果为空则返回0。然后递归计算左子树和右子树的最大深度,并将其分别保存在leftDepth和rightDepth中。最后返回左子树的最大深度和右子树的最大深度中的较大值加1,即为整个二叉树的最大深度。
时间复杂度:O(N)
在最坏情况下,我们需要遍历二叉树的所有节点一次,其中N是二叉树中的节点数量。因此,时间复杂度为O(N)。
空间复杂度:O(H)
在递归的过程中,系统需要使用递归函数的调用栈。在最坏情况下,二叉树是一个单链的结构,递归的深度等于二叉树的高度H。因此,空间复杂度为O(H)。
三、编程语言:
java
四、正确代码:
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
return Math.max(leftDepth, rightDepth) + 1;
}
}

京公网安备 11010502036488号