python力扣刷题——翻转二叉树、对称二叉树（递归法、迭代法）_python 递归翻转二叉树

作者：从前慢现在也慢 | 2024-06-03 11:00:42

踩

python 递归翻转二叉树

1、翻转二叉树：给一棵二叉树的根节点root，翻转这棵二叉树，并返回其根节点

递归法

把每个节点的左右孩子翻转一下，就可以达到整体翻转的效果
如：

# “->”为函数标注，通常用于类型提示，是python3中引入的用法。返回值注解的符号。它通过允许将元数据附加到描述其参数和返回值的函数来扩展该功能。

一个递归函数一般由两部分组成：递归终止的条件、循环体。用一颗最简单的二叉树，确定循环体。每一棵大的二叉树都是由很多的子二叉树组成的。只要子二叉树可以实现目标，递归往上就会使得整个树都实现目标。

前序遍历指根结点在最前面输出，前序遍历的顺序是：中左右


class TreeNode:
    # 二叉树的节点结构，包括存储数据、左指针、右指针
    def __init__(self, val=0, left=None, right=None, ):    
        self.val = val
        self.left = left
        self.right = right
 
class Solution:
    def inverTree(self, root: TreeNode) -> TreeNode:
        # 设立递归终止的条件：如果root节点为空，就返回
        if not root:  
            return None
        root.left, root.right = root.right, root.left  # 中 交换左右两个儿子
        # 然后递归遍历
        self.inverTree(root.left)  # 先反转左子树的子节点
        self.inverTree(root.right)  # 再反转右子树的子节点
        # 返回结果
        return root

树的遍历方式总体分为两类：深度优先搜索（DFS）、广度优先搜索（BFS）：

常见的 DFS ：先序遍历、中序遍历、后序遍历（递归法）；
常见的 BFS ：层序遍历（即按层遍历，迭代法）。

要求：从上到下打印二叉树，同层节点按照从左往右的顺序打印，即树的广度优先搜索（BFS）。
思路：运用队列结构的思想，将同一层的节点加到队列中，每次在结果集中追加同一层节点的val。

层序遍历，迭代法


# from collections import deque # deque()是双端列表，即两端都可以进行插入和删除操作 
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return None
        # que =deque([root])    # 创建一个队列,队列添加一个可迭代元素：列表
        que = []  # 利用队列，层次遍历二叉树
        que.append(root)  # 初始化，加入根节点
        while que:
            size = len(que)
            for i in range(size):
                # node = que.popleft()  # appendleft()：在队列的左侧添加元素
                node = que.pop()    # 使用pop()方法来弹出队列元素。
                node.left, node.right = node.right, node.left   # 节点处理 交换
                if node.left: 
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
        return root

2、对称二叉树：给你一个二叉树的根节点root，检查它是否轴对称

【input】root=[1,2,2,3,4,4,3]

【output】true

这个[1,2,2,null,3,null,3]就不是镜像对称

对称二叉树的左右子树关于根节点对称，对于一棵对称二叉树的每一棵子树，以穿过根节点的直线为对称轴，左边子树的左节点=右边子树的右节点，左边子树的右节点=左边子树的左节点。所以对称二叉树的定义是针对一棵树，而判断的操作是针对节点，这时可以采取由上到下的顺序，从根节点依次向下判断，只需要重复调用函数，不需要回溯。

1、非递归解法：按层遍历，每一层检查一下是否对称。

2、递归解法：

其中左子树和右子树对称的条件：

两个节点值相等，或者都为空
左节点的左子树和右节点的右子树对称
左节点的右子树和右节点的左子树对称

利用递归的思想，将左子树的左边和右子树的右边做为函数的输入，进行判断，不断递归，同理将左子树的右边和右子树的左边作为输出同时返回结果

递归


class Soiution:
    def isSymmetric(self,root:TreeNode)->bool:
        if not root:
            return True
        return self.compare(root.left,root.right)
    def compare(self,left,right):
        if not left or not right:   # 一个存在一个不存在
            return False
        elif not left and not right:    # 两个都不存在
            return True
        elif left.val != right.val:     # 值不相等
            return False
        return self.compare(left.left,right.right) and self.compare(left.right,right.left)  # 两次对比，二叉树一个节点最多有两个子节点

迭代

主要思想是层序遍历判断每一层节点的值构成的数组是否是回文数组。

左子树的左节点与右子树的右节点相等，左子树的右节点与右子树的左节点相等


class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        nodes = [root]      # 定义一个列表nodes获得上次循环的next_nodes，初始为nodes = [root]
        while nodes:
            values = []     # values列表保存当前遍历层节点的值
            next_nodes = []     # 列表保存当前层下一层的节点
            for node in nodes:
                if node:
                    values.append(node.val)     # 当nodes中节点非空节点，values添加该节点的值
                    next_nodes.append(node.left)    # next_nodes依次添加该节点的左右孩子节点（层序遍历思想）
                    next_nodes.append(node.right)
                else:
                    values.append(None)     # 当节点为空节点的时候则values添加None
            if values != values[::-1]:
                return False
            nodes = next_nodes
        return True