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