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 None

    root.left, root.right = root.right, root.left
    invertTreePreOrder(root.left)
    invertTreePreOrder(root.right)

    return root

中序：

def invertTreeInOrder(root):
    if not root:
        return None

    invertTreeInOrder(root.left)
    root.left, root.right = root.right, root.left
    invertTreeInOrder(root.left)  # 注意：这里应该再次调用左子树

    return root

在中序遍历中，我们先递归地处理左子树，然后交换当前节点的左右子节点，最后处理右子树。注意，由于我们在交换后再递归右子树，实际上我们需要两次递归左子树。

中序 法2：

def invertTree(root):
    if not root:
        return root

    right = root.right  # 先把右子树存起来

    # 左
    invertTree(root.left)

    # 根
    root.left, root.right = root.right, root.left

    # 右
    invertTree(right)

    return root

后序：

def invertTreePostOrder(root):
    if not root:
        return None

    invertTreePostOrder(root.left)
    invertTreePostOrder(root.right)
    root.left, root.right = root.right, root.left

    return root

层序遍历

def inverTree(root):
    if not root:
        return root
    queque_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 True
    return compare(root.left, root.right)

def compare(left, right):
    if not left and not right:
        return True
    if not left:
        return False
    if not right:
        return False
    if left.val != right.val:
        return False
    con1 = compare(left.left, right.right)
    con2 = compare(left.right, right.left)
    if con1 and con2:
        return True
    return False

迭代法

使用栈

def isSymmetric(root):
    if not root:
        return True
    stack_record = [(root.left, root.right)]
    while stack_record:
        left, right = stack_record.pop()
        if not left and not right:
            continue   # 不能直接return True
        if not left:
            return False
        if not right:
            return False
        if left.val != right.val:
            return False
        stack_record.append([left.left, right.right])
        stack_record.append([left.right, right.left])
    return True

使用队列：

def isSymmetric(root):
    if not root:
        return True
    queue_record = [(root.left, root.right)]
    while queue_record:
        left, right = queue_record.pop(0)
        if not left and not right:
            continue   # 不能直接return True
        if not left:
            return False
        if not right:
            return False
        if left.val != right.val:
            return False
        queue_record.append([left.left, right.right])
        queue_record.append([left.right, right.left])
    return True