题目描述

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1：

输入： root = [3,9,20,null,null,15,7]
输出： 3

示例 2：

输入： root = [1,null,2]
输出： 2

提示：

• 树中节点的数量在 [0, 10⁴] 区间内。
• -100 <= Node.val <= 100

代码及注释

/*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/func maxDepth(root *TreeNode) int {// 如果根节点为空，返回深度0if root == nil {return 0}// 递归计算左子树和右子树的最大深度，然后取最大值并加1return max(maxDepth(root.Left), maxDepth(root.Right)) + 1
}

代码解释

1. 空节点检查:

   if root == nil {return 0
   }
   

   • 如果当前节点 root 为空，那么它的深度为0。

2. 递归计算最大深度:

   return max(maxDepth(root.Left), maxDepth(root.Right)) + 1
   

   • 使用递归的方法计算左子树和右子树的最大深度。
   • 最大深度是左子树和右子树的深度的最大值加1，因为要加上当前的根节点。

3. 辅助函数:

   func max(a, b int) int {if a > b {return a}return b
   }
   

   • 这是一个辅助函数，用于返回两个整数中的最大值。

这个递归的解法的时间复杂度是 O(n)，其中 n 是二叉树的节点数。