Python判断是否镜像对称二叉树

镜像对称二叉树,顾名思义,以根节点为轴,左右节点和节点内容互为镜像;如下图所示。这里要避免和完全二叉树混淆。

Python判断是否镜像对称二叉树

 

这个我还是考虑了一段时间,递归和迭代都可以实现。递归的,如果一个节点值作为输入很难实现,所以新建一个新方法recurse,输入左右两个节点,返回bool值。思路很简单,如果输入两个节点都是空,可能是单个跟节点,返回True;如果一个有,另一个为空,返回False;如果左右两个节点,如果节点值相等,这里递归,把这两个节点的子节点左右对比,并按照and 关联,如果有一个下层对比False,则所有都是False。如果都为True,则层层返回True。

 

递归的核心点,就是定义传入下一次递归输入,和如何处理下一次递归的返回。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if root== None:
            return True
        else:
            return recurse(root.left,root.right)
        
def recurse(leftNode,rightNode):
        if leftNode == None and rightNode == None:
            return True
        elif leftNode != None and rightNode != None:
            if leftNode.val ==rightNode.val:
                return recurse(leftNode.left,rightNode.right) and recurse(leftNode.right,rightNode.left)
            else:
                return False
        else:
            return False

 

Python判断是否镜像对称二叉树

上一篇:37.FFmpeg+OpenCV直播推流(nginx服务器搭建和测试)


下一篇:Android开发10——Activity的跳转与传值_显示意图(intent)的应用