题目
给你一个二叉树的根节点 root ， 检查它是否轴对称。
输入：root = [1,2,2,3,4,4,3]
输出：true
输入：root = [1,2,2,null,3,null,3]
输出：false
题解
考察二叉树的遍历, 使用广度优先 BFS 方法.
BFS 的关键在于使用队列, 遍历树时, 读到的节点先入队, 再出队, 出队时读取值, 放入结果列表.
out = []
queue = []
queue.append(node)
while queue:
this = queue.pop()
# 出队列后, 判断这个元素是否为空, 不为空就先读取值, 再将子节点放入队列.
if this:
out.append(this.val)
# 此处不用判断, 空节点也放入队列, 之后出队列再判断
queue = [this.left] + queue
queue = [this.right] + queue
else:
# 空节点直接输出
out.append(None)
左右对称的判断, 只需要调整子节点入队列的左右顺序即可
完整代码
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
if self.leftFirst(root) == self.rightFirst(root):
return True
else:
return False
# BFS
def leftFirst(self, node):
out = []
queue = []
queue.append(node)
while queue:
this = queue.pop()
if this:
out.append(this.val)
# 不用判断, 空节点也放入队列, 之后输出处理
queue = [this.left] + queue
queue = [this.right] + queue
else:
# 空节点直接输出
out.append(None)
# print(out)
return out
def rightFirst(self, node):
out = []
queue = []
queue.append(node)
while queue:
this = queue.pop()
if this:
out.append(this.val)
queue = [this.right] + queue
queue = [this.left] + queue
else:
out.append(None)
return out