LeetCode-101-对称二叉树（迭代法）（python）

对称二叉树

上一篇写了对称二叉树判断的递归解法：即对称子树需要满足：1.两棵子树根节点值相等 2. 左右子树镜像对称
这一篇讲解对称二叉树的迭代解法：主要思想是层序遍历判断每一层节点的值构成的数组是否是回文数组。

1. 需要一个列表保存当前遍历层节点的值（layer）
2. 需要一个列表保存当前层下一层的节点（next_queue）
3. 定义一个列表queue获得上次循环的next_queue，初始为queue = [root]
4. 当queue中节点非空节点，layer添加该节点的值，next_queue依次添加该节点的左右孩子节点（层序遍历思想）；当节点为空节点的时候则layer添加None，这样最后一层的遍历完的时候，layer中的元素由于都是None，则next_queue不会添加任何节点，queue = next_queue = [ ]，退出while循环，若之前未return False，则return True，程序结束。

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        queue = [root]
        while queue:
            layer = []
            next_queue = []
            for node in queue:
                if not node:
                    layer.append(None)
                    continue

                layer.append(node.val)
                next_queue.append(node.left)
                next_queue.append(node.right)

            if layer != layer[::-1]:
                return False
            queue = next_queue
        return True