本文为Python算法题集之一的代码示例

题104：二叉树的最大深度

1. 示例说明

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

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

  示例 1：

  

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

  示例 2：

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

  提示：

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

---

2. 题目解析

- 题意分解

1. 本题为求二叉树的最大深度
2. 基本的解法是深度优先算法【DFS】、广度有限算法【BFS】

- 优化思路

1. 通常优化：减少循环层次

2. 通常优化：增加分支，减少计算集

3. 通常优化：采用内置算法来提升计算速度

4. 分析题目特点，分析最优解

   1. 可以用递归法实现深度优先【Depth-First Search】算法

   2. 可以用双向队列deque来实现广度优先【Breadth-First Search】算法

---

- 测量工具

• 本地化测试说明：LeetCode网站测试运行时数据波动很大，因此需要本地化测试解决这个问题
• CheckFuncPerf（本地化函数用时和内存占用测试模块）已上传到CSDN，地址：Python算法题集_检测函数用时和内存占用的模块
• 本题本地化超时测试用例自己生成，详见【最优算法章节】

---

3. 代码展开

1) 标准求解【DFS+自顶向下】

自顶向下的深度优先算法

马马虎虎，超过59%

import CheckFuncPerf as cfpclass Solution:def maxDepth_base(self, root):def topdown(node, ilevel):if not node:return ilevelreturn  max(topdown(node.left, ilevel + 1), topdown(node.right, ilevel + 1))return topdown(root, 0)aroot = generate_binary_tree(ilen, imode)
aSolution = Solution()
result = cfp.getTimeMemoryStr(Solution.maxDepth_base, aSolution, aroot)
print(result['msg'], '执行结果 = {}'.format(result['result']))# 运行结果
函数 maxDepth_base 的运行时间为 424.10 ms；内存使用量为 4.00 KB 执行结果 = 52

2) 改进版一【DFS+自底向上】

自底向上的深度优先算法

马马虎虎，超过73%

import CheckFuncPerf as cfpclass Solution:def maxDepth_ext1(self, root):def bottomup(node):if not node:return 0return max(bottomup(node.left), bottomup(node.right)) + 1return bottomup(root)aroot = generate_binary_tree(ilen, imode)
aSolution = Solution()
result = cfp.getTimeMemoryStr(Solution.maxDepth_ext1, aSolution, aroot)
print(result['msg'], '执行结果 = {}'.format(result['result']))# 运行结果
函数 maxDepth_ext1 的运行时间为 390.09 ms；内存使用量为 0.00 KB 执行结果 = 52

3) 改进版二【BFS】

使用双端队列deque 来实现广度优先算法

性能优良，超过89%

import CheckFuncPerf as cfpclass Solution:def maxDepth_ext2(self, root):from collections import dequeif root is None:return 0deque_tree = deque([root])ilevel = 0while deque_tree:ilen = len(deque_tree)for iIdx in range(ilen):tmpNode = deque_tree.popleft()if tmpNode.left is not None:deque_tree.append(tmpNode.left)if tmpNode.right is not None:deque_tree.append(tmpNode.right)ilevel += 1return ilevelaroot = generate_binary_tree(ilen, imode)
aSolution = Solution()
result = cfp.getTimeMemoryStr(Solution.maxDepth_ext2, aSolution, aroot)
print(result['msg'], '执行结果 = {}'.format(result['result']))# 运行结果
函数 maxDepth_ext2 的运行时间为 390.09 ms；内存使用量为 0.00 KB 执行结果 = 52

---

4. 最优算法

根据本地日志分析，最优算法为第3种【BFS】maxDepth_ext2

import random
ilen, imode = 1000000, 1
def generate_binary_tree(node_count, imode):if node_count <= 0:return Noneroot = TreeNode(random.randint(1, 100))node_count -= 1if imode > 3:imode = 1if imode == 1:left = generate_binary_tree(node_count // 2, imode+1)right = generate_binary_tree(node_count // 2, imode+1)root.left = leftroot.right = rightelif imode==2:left = generate_binary_tree(node_count, imode+1)root.left = leftelse:right = generate_binary_tree(node_count, imode+1)root.right = rightreturn root
aroot = generate_binary_tree(ilen, imode)
aSolution = Solution()
result = cfp.getTimeMemoryStr(Solution.maxDepth_base, aSolution, aroot)
print(result['msg'], '执行结果 = {}'.format(result['result']))
result = cfp.getTimeMemoryStr(Solution.maxDepth_ext1, aSolution, aroot)
print(result['msg'], '执行结果 = {}'.format(result['result']))
result = cfp.getTimeMemoryStr(Solution.maxDepth_ext2, aSolution, aroot)
print(result['msg'], '执行结果 = {}'.format(result['result']))# 算法本地速度实测比较
函数 maxDepth_base 的运行时间为 424.10 ms；内存使用量为 4.00 KB 执行结果 = 52
函数 maxDepth_ext1 的运行时间为 390.09 ms；内存使用量为 0.00 KB 执行结果 = 52
函数 maxDepth_ext2 的运行时间为 386.09 ms；内存使用量为 992.00 KB 执行结果 = 52

一日练，一日功，一日不练十日空

may the odds be ever in your favor ~