【leetcode系列】Python实现二叉树层次遍历和判断一颗二叉树是否是镜像树

落日映苍穹つ 2022-12-08 14:12 102阅读 0赞

## Python实现二叉树层次遍历和判断一颗二叉树是否是镜像树‘ ##

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

### 题目背景介绍： ###

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

![0dcb2b176246d0831acd79bb2429d4c6.png][]

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

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

### 代码实现二叉树层次遍历输出和判断二叉树是否为镜像树 ###

# -*- coding:utf-8 -*-
    '''
    二叉树层次遍历和判断一颗二叉树是否是镜像树
    '''
    
    
    class Solution1():
        def levelOrderBottom(self, root):
            '''
            实现二叉树层次遍历
            :param root:
            :return:
            '''
            if root == None:
                return []
            queue = [root]
            result = []
            while queue:
                temp = []
                for i in range(len(queue)):
                    tempNode = queue.pop(0)
                    temp.append(tempNode.val)
                    if tempNode.left:
                        queue.append(tempNode.left)
                    if tempNode.right:
                        queue.append(tempNode.right)
                result.append(temp)
            print result
            # result.reverse()  # 倒序
            return result
    
    
    class TreeNode:
        def __init__(self, x):
            '''
            构造二叉树结点
            :param x:
            '''
            self.val = x
            self.left = None
            self.right = None
    
    
    def fun_recurse(left_node, right_node):
        '''
        判断左子树和右子树是否是镜像
        :param left_node: 
        :param right_node: 
        :return: 
        '''
        if left_node == None and right_node == None:
            return True
        elif left_node != None and right_node != None:
            if left_node.val == right_node.val:
                return fun_recurse(left_node.left, right_node.right) and fun_recurse(left_node.right, right_node.left)
            else:
                return False
        else:
            return False
        
    
    def fun_is_mirror(root):
        '''
        判断传入的二叉树是否是镜像二叉树
        :param root:
        :return:
        '''
        if root == None:
            return True
        else:
            return fun_recurse(root.left, root.right)
    
    
    if __name__ == '__main__':
        # 构造普通二叉树 1
        # A, B, C, D, E, F, G, H, I = [TreeNode(x) for x in 'ABCDEFGHI']
        # A.left, A.right = B, C
        # B.right = D
        # C.left, C.right = E, F
        # E.left = G
        # F.left, F.right = H, I
        # # print C.right
        # obj_1=Solution1()
        # final_list = obj_1.levelOrderBottom(A)
        # for e in final_list:
        #     # print e
        #     print " ".join(e)
        # print fun_is_mirror(A)
        '''
        [['A'], ['B', 'C'], ['D', 'E', 'F'], ['G', 'H', 'I']]
        A
        B C
        D E F
        G H I
        False
        '''
    
        # 构造二叉镜像树 2
        # A, B, C, D, E, F, G, = [TreeNode(x) for x in '1223443']
        # A.left, A.right = B, C
        # B.left, B.right = D, E
        # C.left, C.right = F, G
        # obj_1 = Solution1()
        # final_list = obj_1.levelOrderBottom(A)
        # for e in final_list:
        #     # print e
        #     print " ".join(e)
        # print fun_is_mirror(A)
        '''
        [['1'], ['2', '2'], ['3', '4', '4', '3']]
        1
        2 2
        3 4 4 3
        True
        '''
    
        # # 构造二叉镜像树 3
        # A, B, C, D, E, F, G, H, I, J, K, M = [TreeNode(x) for x in '122344356657']
        # A.left, A.right = B, C
        # B.left, B.right = D, E
        # C.left, C.right = F, G
        # D.left, D.right = H, I
        # G.left, G.right = J, K
        #
        # obj_1 = Solution1()
        # final_list = obj_1.levelOrderBottom(A)
        # for e in final_list:
        #     # print e
        #     print " ".join(e)
        # print fun_is_mirror(A)
        '''
        [['1'], ['2', '2'], ['3', '4', '4', '3'], ['5', '6', '6', '5']]
        1
        2 2
        3 4 4 3
        5 6 6 5
        True
        '''
    
        # # 构造二叉镜像树 4
        # A, B, C, D, E, F, G, H, I, J, K, M = [TreeNode(x) for x in '122344356657']
        # A.left, A.right = B, C
        # B.left, B.right = D, E
        # C.left, C.right = F, G
        # D.left = H
        # G.right = K
        #
        # obj_1 = Solution1()
        # final_list = obj_1.levelOrderBottom(A)
        # for e in final_list:
        #     # print e
        #     print " ".join(e)
        # print fun_is_mirror(A)
    
        '''
        [['1'], ['2', '2'], ['3', '4', '4', '3'], ['5', '5']]
        1
        2 2
        3 4 4 3
        5 5
        True
        '''
    
        # 构造普通二叉树 5
        A, B, C, D, E, F, G, H, I, J, K, M = [TreeNode(x) for x in '122344356657']
        A.left, A.right = B, C
        B.left, B.right = D, E
        C.left, C.right = F, G
        D.left = H
        G.left, G.right = J,K
    
        obj_1 = Solution1()
        final_list = obj_1.levelOrderBottom(A)
        for e in final_list:
            # print e
            print " ".join(e)
        print fun_is_mirror(A)
    
        '''
        [['1'], ['2', '2'], ['3', '4', '4', '3'], ['5', '6', '5']]
        1
        2 2
        3 4 4 3
        5 6 5
        False
        '''

参考：[http://blog.itpub.net/22259926/viewspace-2674075/][http_blog.itpub.net_22259926_viewspace-2674075]

[0dcb2b176246d0831acd79bb2429d4c6.png]: /images/20221123/0fd69db11e9548e0a4cc9bb6ca1ab122.png
[http_blog.itpub.net_22259926_viewspace-2674075]: http://blog.itpub.net/22259926/viewspace-2674075/