杨和网站设计制作,合肥网站推广培训,wordpress页面的模板,住房和城乡建设部网站事故快报相关推荐 python coding with ChatGPT 打卡第12天| 二叉树#xff1a;理论基础 python coding with ChatGPT 打卡第13天| 二叉树的深度优先遍历 python coding with ChatGPT 打卡第14天| 二叉树的广度优先遍历 文章目录 翻转二叉树Key Points相关题目视频讲解重点分析递归遍历…相关推荐 python coding with ChatGPT 打卡第12天| 二叉树理论基础 python coding with ChatGPT 打卡第13天| 二叉树的深度优先遍历 python coding with ChatGPT 打卡第14天| 二叉树的广度优先遍历 文章目录 翻转二叉树Key Points相关题目视频讲解重点分析递归遍历层序遍历 对称二叉树Key Points相关题目视频讲解重点分析递归法迭代法 翻转二叉树
Key Points
只要把每个节点的左右孩子翻转一下就可以达到整体翻转的效果可选择深度优先遍历递归遍历或广度优先遍历层序遍历
相关题目
226. 翻转二叉树
视频讲解
翻转二叉树
重点分析
递归遍历
前序
def invertTreePreOrder(root):if not root:return Noneroot.left, root.right root.right, root.leftinvertTreePreOrder(root.left)invertTreePreOrder(root.right)return root
中序
def invertTreeInOrder(root):if not root:return NoneinvertTreeInOrder(root.left)root.left, root.right root.right, root.leftinvertTreeInOrder(root.left) # 注意这里应该再次调用左子树return root
在中序遍历中我们先递归地处理左子树然后交换当前节点的左右子节点最后处理右子树。注意由于我们在交换后再递归右子树实际上我们需要两次递归左子树。
中序 法2
def invertTree(root):if not root:return rootright root.right # 先把右子树存起来# 左invertTree(root.left)# 根root.left, root.right root.right, root.left# 右invertTree(right)return root
后序
def invertTreePostOrder(root):if not root:return NoneinvertTreePostOrder(root.left)invertTreePostOrder(root.right)root.left, root.right root.right, root.leftreturn root
层序遍历
def inverTree(root):if not root:return rootqueque_record [root]while queque_record:node queque_record.pop(0)node.left, node.right node.right, node.left # 这里不管是先翻转左右节点还是先加入左右节点都可以if node.left:queque_record.append(node.left)if node.right:queque_record.append(node.right)return root在实现迭代法的过程中有同学问了递归与迭代究竟谁优谁劣呢 从时间复杂度上其实迭代法和递归法差不多在不考虑函数调用开销和函数调用产生的堆栈开销但是空间复杂度上递归开销会大一些因为递归需要系统堆栈存参数返回值等等。 递归更容易让程序员理解但收敛不好容易栈溢出。 这么说吧递归是方便了程序员难为了机器各种保存参数各种进栈出栈。 在实际项目开发的过程中我们是要尽量避免递归因为项目代码参数、调用关系都比较复杂不容易控制递归深度甚至会栈溢出。 对称二叉树
Key Points
二叉树类的题目确定遍历顺序非常重要
相关题目
101. 对称二叉树
视频讲解
同时操作两个二叉树
重点分析
递归法
def isSymmetric(root):if not root:return Truereturn compare(root.left, root.right)def compare(left, right):if not left and not right:return Trueif not left:return Falseif not right:return Falseif left.val ! right.val:return Falsecon1 compare(left.left, right.right)con2 compare(left.right, right.left)if con1 and con2:return Truereturn False迭代法
使用栈
def isSymmetric(root):if not root:return Truestack_record [(root.left, root.right)]while stack_record:left, right stack_record.pop()if not left and not right:continue # 不能直接return Trueif not left:return Falseif not right:return Falseif left.val ! right.val:return Falsestack_record.append([left.left, right.right])stack_record.append([left.right, right.left])return True使用队列
def isSymmetric(root):if not root:return Truequeue_record [(root.left, root.right)]while queue_record:left, right queue_record.pop(0)if not left and not right:continue # 不能直接return Trueif not left:return Falseif not right:return Falseif left.val ! right.val:return Falsequeue_record.append([left.left, right.right])queue_record.append([left.right, right.left])return True
