一、知识点:
递归、二叉树
二、文字分析:
使用了递归的方式来计算二叉树的最大深度。首先判断根节点是否为空,如果为空则返回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; } }