沈阳网站关键字优化,提升学历咨询,网络做推广广告公司,个人如何制作app算法#xff1a;
第一想法是用昨天的层序遍历#xff0c;把每一层level用切片反转。但是这样时间复杂度很高。
其实只要在遍历的过程中去翻转每一个节点的左右孩子就可以达到整体翻转的效果。
这道题目使用前序遍历和后序遍历都可以#xff0c;唯独中序遍历不方便#x…
算法
第一想法是用昨天的层序遍历把每一层level用切片反转。但是这样时间复杂度很高。
其实只要在遍历的过程中去翻转每一个节点的左右孩子就可以达到整体翻转的效果。
这道题目使用前序遍历和后序遍历都可以唯独中序遍历不方便因为中序遍历会把某些节点的左右孩子翻转了两次建议拿纸画一画就理解了
注意是指针进行交换交换的是左右孩子然后里面的值再交换
首先使用递归法代码简单
调试过程: 原因root没有迭代一直都是有值的根节点。有递归了其实不用while循环了。
正确代码
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution:def invertTree(self, root: Optional[TreeNode]) - Optional[TreeNode]:#root是每一个节点变量不一定是根节点if root None:return Noneelse:#交换左右孩子指针Vroot.left, root.right root.right, root.left#L每个子树下面的节点进一步进行左右交换if root.left:root.left self.invertTree(root.left)#R每个子树下面的节点进一步进行左右交换if root.right:root.right self.invertTree(root.right)return root
时间空间复杂度
invertTree函数的时间复杂度是O(n)其中n是二叉树中的节点数。这是因为我们对每个节点进行一次访问并且对每个节点执行固定量的工作。
invertTree函数的空间复杂度是O(h)其中h是二叉树的高度。这是因为函数使用递归递归的最大深度等于树的高度。在最坏的情况下即树完全不平衡且类似于链表的情况下树的高度等于节点数导致空间复杂度为O(n)。然而在平衡的二叉树中高度通常是log(n)导致空间复杂度为O(log(n))。
面试官看你顺畅的写出了递归一般会进一步考察能不能写出相应的迭代
我觉得迭代法就是要加循环
使用迭代的方式来翻转二叉树。我们从根节点开始将根节点入栈。然后进入循环直到栈为空。在循环中我们从栈中弹出一个节点并交换其左右子节点的指针。如果存在左子节点则将其入栈如果存在右子节点则将其入栈。
stack用于迭代地翻转二叉树。它起到了存储待处理节点的作用。
使用栈的迭代方法相比于递归方法可以减少递归调用的开销同时也可以避免递归的最大深度限制。
递归的最大深度限制是什么
递归的最大深度限制是指递归调用的层数上限。每次进行递归调用时系统会在内存中为该函数分配一段栈空间用于保存函数的局部变量、参数和返回地址等信息。当递归的层数过多时栈空间会被耗尽导致栈溢出错误。
不同的编程语言和操作系统对递归的最大深度限制可能有所不同。在Python中默认的最大递归深度是1000层超过这个限制将引发RecursionError异常。可以使用sys.setrecursionlimit()函数来修改Python的递归深度限制但是需要注意修改深度限制可能会导致栈溢出错误。
为了避免递归的最大深度限制可以使用迭代的方法来替代递归或者使用尾递归优化等技术来减少递归调用的层数。
正确代码
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution:def invertTree(self, root: Optional[TreeNode]) - Optional[TreeNode]:#root是根节点if root None:return Noneelse:stack [root]#交换左右孩子指针Vwhile stack:#将node定义为每个节点node stack.pop()#交换node.left, node.right node.right, node.left#L将node.left存入stack这样循环时pop出来进行子节点的交换if node.left:stack.append(node.left) #R每个子树下面的节点进一步进行左右交换if node.right:stack.append(node.right) return root
时间空间复杂度
时间复杂度
遍历每个节点并交换其左右子节点的指针需要O(n)的时间其中n是二叉树中的节点数。
空间复杂度
使用了一个栈来存储待处理节点最坏情况下栈的大小与二叉树的高度成正比即O(h)其中h是二叉树的高度。在最坏情况下当二叉树是一个单链表时树的高度等于节点数因此空间复杂度为O(n)。在平衡的二叉树中树的高度通常是log(n)因此空间复杂度为O(log(n))。
综上所述该解决方案的时间复杂度为O(n)空间复杂度为O(h)或O(n)。
