python coding with ChatGPT 打卡第15天| 二叉树：翻转二叉树、对称二叉树

相关推荐
python coding with ChatGPT 打卡第12天| 二叉树：理论基础
python coding with ChatGPT 打卡第13天| 二叉树的深度优先遍历
python coding with ChatGPT 打卡第14天| 二叉树的广度优先遍历

翻转二叉树

Key Points

1. 只要把每个节点的左右孩子翻转一下，就可以达到整体翻转的效果
2. 可选择深度优先遍历（递归遍历）或广度优先遍历（层序遍历）

相关题目

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