给定一个二叉树,检查它是否是镜像对称的。
例如,二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ \
2 2
/ \ / \
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/ \
2 2
\ \
3 3
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/symmetric-tree
解决该问题主要方法是BFS,在经行层遍历的时候,对每一层进行回文字符串判断,代码如下:
# 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:
stack = [root]
while stack:
next_stack = list()
layer = list()
for node in stack:
if not node:
layer.append(None)
continue
next_stack.append(node.left)
next_stack.append(node.right)
layer.append(node.val)
if layer != layer[::-1]:
return False
stack = next_stack
return True