Python实现二叉树层次遍历和判断一颗二叉树是否是镜像树‘
判断是否镜像对称二叉树。
题目背景介绍:
镜像对称二叉树,顾名思义,以根节点为轴,左右节点和节点内容互为镜像;如下图所示。这里要避免和完全二叉树混淆。
这个我还是考虑了一段时间,递归和迭代都可以实现。递归的,如果一个节点值作为输入很难实现,所以新建一个新方法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
'''
版权声明:本文为helloxiaozhe原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。