网站建设要用到哪些应用工具,建设银行网站怎么不可登入,美容营销型网站,三艺网站建设Python算法题集_翻转二叉树 题226#xff1a;翻转二叉树1. 示例说明2. 题目解析- 题意分解- 优化思路- 测量工具 3. 代码展开1) 标准求解【DFS递归】2) 改进版一【BFS迭代#xff0c;节点循环】3) 改进版二【BFS迭代#xff0c;列表循环】 4. 最优算法 本文为Python算法题集… Python算法题集_翻转二叉树 题226翻转二叉树1. 示例说明2. 题目解析- 题意分解- 优化思路- 测量工具 3. 代码展开1) 标准求解【DFS递归】2) 改进版一【BFS迭代节点循环】3) 改进版二【BFS迭代列表循环】 4. 最优算法 本文为Python算法题集之一的代码示例
题226翻转二叉树
1. 示例说明 示例 1 输入root [4,2,7,1,3,6,9]
输出[4,7,2,9,6,3,1]示例 2 输入root [2,1,3]
输出[2,3,1]示例 3 输入root []
输出[]提示 树中节点数目范围在 [0, 100] 内-100 Node.val 100 2. 题目解析
- 题意分解
本题为二叉树的翻转基本的设计思路是深度优先算法【DFSDepth-First Search】、广度有限算法【BFSBreadth-First Search】
- 优化思路 通常优化减少循环层次 通常优化增加分支减少计算集 通常优化采用内置算法来提升计算速度 分析题目特点分析最优解 可以考虑采用迭代法改写递归函数提高性能 - 测量工具
本地化测试说明LeetCode网站测试运行时数据波动很大因此需要本地化测试解决这个问题CheckFuncPerf本地化函数用时和内存占用测试模块已上传到CSDN地址Python算法题集_检测函数用时和内存占用的模块本题本地化超时测试用例自己生成详见【最优算法章节】 3. 代码展开
1) 标准求解【DFS递归】
采用深度优先算法标准递归实现
马马虎虎超过66%
import CheckFuncPerf as cfpclass Solution:def invertTree_base(self, root):if not root:return Noneroot.left, root.right root.right, root.leftself.invertTree_base(root.left)self.invertTree_base(root.right)return rootaroot generate_binary_tree(ilen)
aSolution Solution()
result cfp.getTimeMemoryStr(Solution.invertTree_base, aSolution, aroot)
print(result[msg], 执行结果 {}.format(result[result].val))# 运行结果
函数 invertTree_base 的运行时间为 600.12 ms内存使用量为 4.00 KB 执行结果 712) 改进版一【BFS迭代节点循环】
通过堆栈结构的迭代算法来改写递归算法单次循环一个节点
性能良好超过82%
import CheckFuncPerf as cfpclass Solution:def invertTree_ext1(self, root):if not root:return Nonestacktree [root]while stacktree:tmpnode stacktree.pop()tmpnode.left, tmpnode.right tmpnode.right, tmpnode.leftif tmpnode.right:stacktree.append(tmpnode.right)if tmpnode.left:stacktree.append(tmpnode.left)return rootaroot generate_binary_tree(ilen)
aSolution Solution()
result cfp.getTimeMemoryStr(Solution.invertTree_ext1, aSolution, aroot)
print(result[msg], 执行结果 {}.format(result[result].val))# 运行结果
函数 invertTree_ext1 的运行时间为 546.13 ms内存使用量为 0.00 KB 执行结果 73) 改进版二【BFS迭代列表循环】
通过队列结构的迭代算法来改写递归算法每次循环一个批次减少了部分循环判断计算
勉强通关超过19%
import CheckFuncPerf as cfpclass Solution:def invertTree_ext2(self, root):if not root:return NonequeueTree [root]while queueTree:for iIdx in range(len(queueTree)):tmpnode queueTree.pop()tmpnode.left, tmpnode.right tmpnode.right, tmpnode.leftif tmpnode.left:queueTree.append(tmpnode.left)if tmpnode.right:queueTree.append(tmpnode.right)return rootaroot generate_binary_tree(ilen)
aSolution Solution()
result cfp.getTimeMemoryStr(Solution.invertTree_ext2, aSolution, aroot)
print(result[msg], 执行结果 {}.format(result[result].val))# 运行结果
函数 invertTree_ext2 的运行时间为 471.11 ms内存使用量为 0.00 KB 执行结果 214. 最优算法
根据本地日志分析最优算法为第3种方式【BFS迭代列表循环】inorderTraversal_ext2
import random
ilen 1000000
def generate_binary_tree(node_count):if node_count 0:return Noneroot TreeNode(random.randint(1, 100))left generate_binary_tree(node_count // 2)right generate_binary_tree(node_count // 2)root.left leftroot.right rightreturn root
aroot generate_binary_tree(ilen)
aSolution Solution()
result cfp.getTimeMemoryStr(Solution.invertTree_base, aSolution, aroot)
print(result[msg], 执行结果 {}.format(result[result].val))
aroot generate_binary_tree(ilen)
result cfp.getTimeMemoryStr(Solution.invertTree_ext1, aSolution, aroot)
print(result[msg], 执行结果 {}.format(result[result].val))
aroot generate_binary_tree(ilen)
result cfp.getTimeMemoryStr(Solution.invertTree_ext2, aSolution, aroot)
print(result[msg], 执行结果 {}.format(result[result].val))# 算法本地速度实测比较
函数 invertTree_base 的运行时间为 600.12 ms内存使用量为 4.00 KB 执行结果 71
函数 invertTree_ext1 的运行时间为 546.13 ms内存使用量为 0.00 KB 执行结果 7
函数 invertTree_ext2 的运行时间为 471.11 ms内存使用量为 0.00 KB 执行结果 21一日练一日功一日不练十日空
may the odds be ever in your favor ~
