Python算法题集_二叉树的最大深度

 Python算法题集_二叉树的最大深度

• 题104：二叉树的最大深度
• 1. 示例说明
• 2. 题目解析
• 3. 代码展开
• 4. 最优算法

本文为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 cfp

class Solution:
 def maxDepth_base(self, root):
     def topdown(node, ilevel):
         if not node:
             return ilevel
         return  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 cfp

class Solution:
 def maxDepth_ext1(self, root):
     def bottomup(node):
         if not node:
             return 0
         return max(bottomup(node.left), bottomup(node.right)) + 1
     return 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 cfp

class Solution:
 def maxDepth_ext2(self, root):
     from collections import deque
     if root is None:
         return 0
     deque_tree = deque([root])
     ilevel = 0
     while 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 += 1
     return ilevel

aroot = 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 None
    root = TreeNode(random.randint(1, 100))
    node_count -= 1
    if imode > 3:
        imode = 1
    if imode == 1:
        left = generate_binary_tree(node_count // 2, imode+1)
        right = generate_binary_tree(node_count // 2, imode+1)
        root.left = left
        root.right = right
    elif imode==2:
        left = generate_binary_tree(node_count, imode+1)
        root.left = left
    else:
        right = generate_binary_tree(node_count, imode+1)
        root.right = right
    return 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 ~