游戏充值网站怎么做,网站被挂马怎么办,网站关键字优化公司,网络营销顾问是什么作者介绍#xff1a;10年大厂数据\经营分析经验#xff0c;现任大厂数据部门负责人。 会一些的技术#xff1a;数据分析、算法、SQL、大数据相关、python 欢迎加入社区#xff1a;码上找工作 作者专栏每日更新#xff1a; LeetCode解锁1000题: 打怪升级之旅 python数据分析… 作者介绍10年大厂数据\经营分析经验现任大厂数据部门负责人。 会一些的技术数据分析、算法、SQL、大数据相关、python 欢迎加入社区码上找工作 作者专栏每日更新 LeetCode解锁1000题: 打怪升级之旅 python数据分析可视化企业实战案例 python源码解读 程序员必备的数学知识与应用 题目描述
给定一个二叉树原地将它展开为一个单链表。例如给定二叉树 1/ \2 5/ \ \
3 4 6展开后应该变为
1\2\3\4\5\6方法一递归展开
解题步骤
如果树为空直接返回。递归展开左子树和右子树。将左子树插入到右子树的位置。将原来的右子树接到当前右子树的末端。考虑到展开后没有左子节点将左子节点设置为None。
代码示例
class Solution:def flatten(self, root):if not root:returnself.flatten(root.left)self.flatten(root.right)# 左右子树已经被拉平成一条链表left root.leftright root.right# 将左子树作为右子树root.left Noneroot.right left# 找到当前右子树原左子树的末端并连接原右子树p rootwhile p.right:p p.rightp.right right方法一的改进主要可以从两个方面进行优化递归效率和空间使用。虽然基本递归方法简单直观但它可能导致不必要的栈空间消耗尤其是在处理非常深的树时可能会导致栈溢出。以下是几种改进策略
改进1: 尾递归优化
虽然Python默认不支持尾递归优化但我们可以尽可能减少递归中不必要的操作将必要的操作移至递归调用之前执行减少递归调用栈的深度。
改进代码示例
class Solution:def flatten(self, root):def flattenTree(node):if not node:return None# 如果节点是叶子节点直接返回if not node.left and not node.right:return node# 递归平展左子树leftTail flattenTree(node.left)rightTail flattenTree(node.right)# 将左子树插入到右子树的地方if leftTail:leftTail.right node.rightnode.right node.leftnode.left None# 返回最后的尾部节点return rightTail if rightTail else leftTailflattenTree(root)改进2: 减少递归深度
尽可能地在每个节点处理完毕后立即释放其左子树的引用减少Python垃圾回收器的压力并减少递归深度。
改进代码示例
class Solution:def flatten(self, root):# Helper function to perform flatten operationdef flattenNode(node):if not node:return None# Flatten the left and right subtreeleft_last flattenNode(node.left)right_last flattenNode(node.right)# If there is a left subtree, weave it into the right subtreeif left_last:left_last.right node.rightnode.right node.leftnode.left None# The rightmost node is needed for linking to the parent nodes right subtreereturn right_last if right_last else left_lastflattenNode(root)方法二迭代展开
解题步骤
使用栈来辅助迭代过程。每次取出栈顶元素如果有右子节点先压栈再压左子节点。修改每个节点的右指针指向下一个栈顶元素左指针设置为None。
代码示例
class Solution:def flatten(self, root):if not root:returnstack [root]prev Nonewhile stack:curr stack.pop()if prev:prev.right currprev.left Noneif curr.right:stack.append(curr.right)if curr.left:stack.append(curr.left)prev curr方法三寻找前驱节点
解题步骤
对于每个节点如果左子节点不为空找到左子树的最右节点前驱节点。将原右子树接到前驱节点的右边。将左子树移到右边左子树置为空。继续处理链表中的下一个节点。
代码示例
class Solution:def flatten(self, root):curr rootwhile curr:if curr.left:pre curr.leftwhile pre.right:pre pre.rightpre.right curr.rightcurr.right curr.leftcurr.left Nonecurr curr.right算法分析
时间复杂度 递归展开(O(n))每个节点访问一次。迭代展开(O(n))每个节点访问一次。寻找前驱节点(O(n))每个节点访问一次。 空间复杂度 递归展开(O(n))递归栈的空间。迭代展开(O(n))使用了额外的栈。寻找前驱节点(O(1))原地修改不需要额外空间。
优劣势对比
递归展开 优点实现简单直观。缺点需要额外的栈空间来处理递归。 迭代展开 优点避免了递归可能导致的栈溢出。缺点需要使用栈来存储节点。 寻找前驱节点 优点不需要额外空间空间复杂度最优。缺点代码逻辑相对复杂需要处理更多的指针操作。
应用示例
这种技巧在处理需要将树结构线性化处理的场景非常有用例如在图形界面开发中需要按特定顺序访问或显示节点信息或者在需要频繁查找、更新结点而又不频繁修改树结构的数据库和文件系统中。
