104. 二叉树的最大深度

题目描述：

给定一个二叉树，找出其最大深度。

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

说明: 叶子节点是指没有子节点的节点。

测试用例：

示例1：

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

示例2：

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

提示：

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

---

解题分析及思路：

本题可以采用分治法进行深度优先搜索。

• 分：可以将左右两个节点拆分为同等的子集
• 治：判断终止条件并计算
• 合：根据左右节点返回的最大深度来计算当前节点的子树的最大深度

代码分析：

• 分的操作：将左右两个节点拆分。

l := maxDepth(root.Left)
r := maxDepth(root.Right)

• 治的操作：当前访问到的节点为空时，返回0值，代表此节点的子树深度为0。

if root == nil {
	return 0
}

• 合的操作：根据左右节点返回的最大深度来计算当前节点的子树的最大深度，如果左子节点的子树深度大于右子节点的子树深度，返回左子节点的子树深度 + 1，否则返回右子节点的子树深度 + 1

if l < r {
    return r + 1
}
return l + 1

复杂度：

• 时间复杂度：O(n ^ 2)
• 空间复杂度：O(1)

执行结果：

• 执行用时： 4 ms , 在所有 Go 提交中击败了 85.62% 的用户
• 内存消耗： 4 MB , 在所有 Go 提交中击败了 98.73% 的用户