【算法】二叉树的最大深度

题目难度：简单[1]

题目描述：

给定一个二叉树，找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 说明: 叶子节点是指没有子节点的节点。

测试用例：

示例：

给定二叉树 [3,9,20,null,null,15,7]，

   3
  / \
 9  20
   /  \
  15   7

返回它的最大深度 3

解题分析及思路：

本题可以采用分治法[2]进行深度优先遍历。

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

代码分析：

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

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

源代码：最小绝对差[3]

复杂度：

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

执行结果：

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

参考资料

[1]

简单最小绝对差: https://leetcode.cn/problems/maximum-depth-of-binary-tree/

[2]

分治法: https://algorithm.lomtom.cn/method/dac

[3]

源代码: https://github.com/lomtom/algorithm-go/blob/main/leetcode/example