leetcode 101 对称二叉树 Simple

题目

给你一个二叉树的根节点 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