题 28：对称二叉树

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。——《剑指 Offer》P159

例如对于如图所示二叉树是对称二叉树。

例如对于如图所示二叉树不是对称二叉树。

二叉树结点定义为：

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

迭代

层序遍历

解题思路

需要使用队列实现层序遍历，依次获取单层的所有结点存入一个线性表中，然后判断这个线性表是否对称就行。关键在于队列中的结点可能是 null 结点，需要对这种情况单独做下判断。

题解代码

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        que = [root]
        while len(que) != 0:
            new_que = []
            for i in range(len(que)):
                if que[i] != None:
                    new_que.append(que[i].left)
                    new_que.append(que[i].right)

            length = len(new_que)
            for i in range(int(length / 2)):
                if new_que[i] == None and new_que[length - i - 1] == None:
                    continue
                if new_que[i] == None or new_que[length - i - 1] == None:
                    return False
                if new_que[i].val != new_que[length - i - 1].val:
                    return False
            que = new_que
        return True

BFS

解题思路

除了一次性获取整层的结点，也可以用 BFS 进行搜索，如果用 BFS 需要保证队列头的 2 个结点是这层中对称的 2 个结点。例如对于图中的二叉树，标为蓝色的 2 个结点分别是这一层结点的对称位置且值相等，说明这 2 个结点是对称的。

设左边的结点是 node1，右边的结点是 node2，只需要按照 node1 的 left、node2 的 right、node1 的 right、node2 的 left 这个顺序入队列，就可以保证 2 个需要被判断的结点在队列头。在上图中的二叉树根据定义，需要被判断的结点对是 A 和 D、B 和 C，按照上述方式入队列就可以保证这种顺序。

题解代码

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if root is None:
            return True

        que = [root.left, root.right]
        while len(que) != 0:
            node1 = que.pop(0)
            node2 = que.pop(0)
            if node1 == None and node2 == None:
                continue
            if node1 == None or node2 == None:
                return False
            if node1.val != node2.val:
                return False
            que.append(node1.left)
            que.append(node2.right)
            que.append(node1.right)
            que.append(node2.left)
        return True

时空复杂度

由于需要遍历所有结点，且需要队列存储待判断的结点，因此时间复杂度和空间复杂度都是 O(n)。

递归

解题思路

从上面的 BFS 可以看出判断了 2 个结点是对称时，设左边的结点是 node1，右边的结点是 node2，只需要再判断 node1 的 left 和 node2 的 right、node1 的 right 和 node2 的 left 是对称的就可以判断是否对称。根据这个结论可以设计出递归函数，递归的出口是 2 个被判断结点的值不相等或一个为 null 另一个不为 null 返回 false，2 个结点都为 null 返回 true。

题解代码

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        flag = True
        if root != None:
            flag = self.judgeNode(root.left, root.right)
        return flag
    
    def judgeNode(self, node1, node2):
        if node1 is None and node2 is None:
            return True
        if node1 is None or node2 is None:
            return False
        if node1.val != node2.val:
            return False
        return self.judgeNode(node1.left, node2.right) and self.judgeNode(node1.right, node2.left)

时空复杂度

由于需要遍历所有结点，因此时间复杂度和空间复杂度都是 O(n)。

参考资料

《剑指 Offer(第2版)》，何海涛著，电子工业出版社
C++与Python两种解法实现：递归与迭代