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

补充：

递归与迭代的关系

1） 递归中一定有迭代,但是迭代中不一定有递归,大部分可以相互转换。

2） 能用迭代的不用递归,递归调用函数,浪费空间,并且递归太深容易造成堆栈的溢出.

用迭代解决，实现堆数据结构，一种非线性数据结构，其中操作按 LIFO（后进先出）顺序执行。将首先访问根值，然后访问左子树，最后访问右子树值。右孩子首先被推入堆栈，然后是左孩子。这是因为堆栈的 LIFO 特性。这样做将允许我们先访问左孩子，然后再访问右孩子。

• 我们将初始化两个列表 IE 一个承载输出，另一个充当我们的堆栈数据结构。堆栈将使用二叉树的根值进行初始化。
• 然后，只要堆栈有值，我们就会在堆栈上执行一个 while 循环。在循环中，依次进行以下操作：
• 删除（弹出）堆栈中最顶部的值（根节点）并将其附加到输出列表
• 将弹出值的右孩子压入堆栈
• 将弹出值的左孩子压入堆栈
• 返回循环结束时的输出列表

参考：

python之队列学习_hedgehog"的博客-CSDN博客

python二叉树类及其遍历的实现是怎样的呢-群英

python实现二叉树的层序、前序、中序、后序、之字形遍历_hedgehog"的博客-CSDN博客

力扣刷题-python-二叉树系列 - 知乎

趣味算法思想 -- 递归与二叉查找树(BST) - 知乎

python创建二叉树及前中后序、层次遍历_楊木木8023的博客-CSDN博客_用python采用二叉链存储结构创建二叉树,实现中序遍历

python中def函数右侧有个-＞的含义_蓝天居士的博客-CSDN博客_python def ->

二叉树(前序，中序，后序，层序)遍历递归与循环的python实现

LeetCode-101-对称二叉树（迭代法）（python） - 简书

https://www.jb51.net/article/261804.htm