一、知识点:

递归、二叉树

二、文字分析:

使用了递归的方式来计算二叉树的最大深度。首先判断根节点是否为空,如果为空则返回0。然后递归计算左子树和右子树的最大深度,并将其分别保存在leftDepthrightDepth中。最后返回左子树的最大深度和右子树的最大深度中的较大值加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;
    }
}