Python算法题集_二叉树的直径
本文为Python算法题集之一的代码示例
题543:二叉树的直径
1. 示例说明
给你一棵二叉树的根节点,返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点
root
。两节点之间路径的 长度 由它们之间边数表示。
示例 1:
输入:root = [1,2,3,4,5]
输出:3
解释:3 ,取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。
示例 2:
输入:root = [1,2]
输出:1
提示:
- 树中节点数目在范围
[1, 104]
内 -100 <= Node.val <= 100
2. 题目解析
- 题意分解
- 本题为检查二叉树中任意两个节点的最长距离
- 基本的设计思路是深度优先算法【DFS(Depth-First Search)】
- 优化思路
通常优化:减少循环层次
通常优化:增加分支,减少计算集
通常优化:采用内置算法来提升计算速度
分析题目特点,分析最优解
本地需要采用
DFS
进行路径长度计算可以考虑在递归函数中使用可变量【通过引用传递】
可以考虑在递归函数中返回最大值【通过值传递】
- 测量工具
- 本地化测试说明:LeetCode网站测试运行时数据波动很大,因此需要本地化测试解决这个问题
CheckFuncPerf
(本地化函数用时和内存占用测试模块)已上传到CSDN,地址:Python算法题集_检测函数用时和内存占用的模块- 本题本地化超时测试用例自己生成,详见【最优算法章节】
3. 代码展开
1) 标准求解【DFS+字典引用】
使用可变量字典传递最长路径长度
性能良好,超过86%
import CheckFuncPerf as cfp
class Solution:
def diameterOfBinaryTre_base(self, root):
def getdepth(root, dictmax):
if not root:
return 0
leftdepth = getdepth(root.left, dictmax)
rightdepth = getdepth(root.right, dictmax)
dictmax['maxlen'] = max(dictmax['maxlen'], leftdepth + rightdepth)
return max(leftdepth, rightdepth) + 1
dictmax = {
'maxlen': 0}
getdepth(root, dictmax)
return dictmax['maxlen']
aroot = generate_binary_tree(ilen, imode)
aSolution = Solution()
result = cfp.getTimeMemoryStr(Solution.diameterOfBinaryTre_base, aSolution, aroot)
print(result['msg'], '执行结果 = {}'.format(result['result']))
# 运行结果
函数 diameterOfBinaryTre_base 的运行时间为 924.05 ms;内存使用量为 4.00 KB 执行结果 = 102
2) 改进版一【DFS+全局变量】
使用全局变量列表传递最长路径长度
马马虎虎,超过51%
import CheckFuncPerf as cfp
class Solution:
def diameterOfBinaryTre_ext1(self, root):
imaxlen = [0]
def getdepth(root):
if not root:
return 0
leftdepth = getdepth(root.left)
rightdepth = getdepth(root.right)
imaxlen[0] = max(imaxlen[0], leftdepth + rightdepth)
return max(leftdepth, rightdepth) + 1
getdepth(root)
return imaxlen[0]
aroot = generate_binary_tree(ilen, imode)
aSolution = Solution()
result = cfp.getTimeMemoryStr(Solution.diameterOfBinaryTre_ext1, aSolution, aroot)
print(result['msg'], '执行结果 = {}'.format(result['result']))
# 运行结果
函数 diameterOfBinaryTre_ext1 的运行时间为 583.67 ms;内存使用量为 0.00 KB 执行结果 = 102
3) 改进版二【DFS+递归返回】
使用递归函数返回值传递最长路径长度
马马虎虎,超过65%
import CheckFuncPerf as cfp
class Solution:
def diameterOfBinaryTre_ext2(self, root):
def getdepth(root):
if root is None:
return 0, 0
left_depth, left_max = getdepth(root.left)
right_depth, right_max = getdepth(root.right)
depth = 1 + max(left_depth, right_depth)
imaxlen = max(left_max, right_max, left_depth + right_depth)
return depth, imaxlen
depth, imaxlen = getdepth(root)
return imaxlen
aroot = generate_binary_tree(ilen, imode)
aSolution = Solution()
result = cfp.getTimeMemoryStr(Solution.diameterOfBinaryTre_ext2, aSolution, aroot)
print(result['msg'], '执行结果 = {}'.format(result['result']))
# 运行结果
函数 diameterOfBinaryTre_ext2 的运行时间为 425.10 ms;内存使用量为 0.00 KB 执行结果 = 102
4. 最优算法
根据本地日志分析,最优算法为第3种方式【DFS+递归返回】isSymmetric_base
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.diameterOfBinaryTre_base, aSolution, aroot)
print(result['msg'], '执行结果 = {}'.format(result['result']))
result = cfp.getTimeMemoryStr(Solution.diameterOfBinaryTre_ext1, aSolution, aroot)
print(result['msg'], '执行结果 = {}'.format(result['result']))
result = cfp.getTimeMemoryStr(Solution.diameterOfBinaryTre_ext2, aSolution, aroot)
print(result['msg'], '执行结果 = {}'.format(result['result']))
# 算法本地速度实测比较
函数 diameterOfBinaryTre_base 的运行时间为 924.05 ms;内存使用量为 4.00 KB 执行结果 = 102
函数 diameterOfBinaryTre_ext1 的运行时间为 583.67 ms;内存使用量为 0.00 KB 执行结果 = 102
函数 diameterOfBinaryTre_ext2 的运行时间为 425.10 ms;内存使用量为 0.00 KB 执行结果 = 102
一日练,一日功,一日不练十日空
may the odds be ever in your favor ~