树-101镜像树-简单-20210813

1. 题目描述

给定一个二叉树，检查它是否是镜像对称的。

示例：

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3

         1
      /     \
    2         2
   / \       / \
  3   4     4   3
 / \ / \   / \ / \
8  7 6  5 5  6 7  8

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

    1
   / \
  2   2
   \   \
   3    3

你可以运用递归和迭代两种方法解决这个问题吗？

2. 题目解答

2.1 递归-深度搜索

满足条件：

• 它们的两个根结点具有相同的值【比较 left 的左节点和 right 的右节点，再比较 left 的右节点和 right 的左节点】
• 每个树的右子树都与另一个树的左子树镜像对称【将根节点的左子树记做 left，右子树记做 right。比较 left 是否等于 right】

终止条件：

• 左右都为空，True
• 其中一个为空，False
• 左右不相等，False

时间复杂度：O(n)，因为要遍历 n个节点
空间复杂度：O(n)，空间复杂度是递归的深度，也就是跟树高度有关，最坏情况下树变成一个链表结构，高度是n

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root: return True
        def dfs(left, right):
            if not left and not right:
                return True  # not (left or right)
            if not left or not right:
                return False  # not (left and right)
            if left.val != right.val:
                return False
            return dfs(left.left, right.right) and dfs(left.right, right.left)
        return dfs(root.left, root.right)

2.2 迭代-广度搜索

初始化时我们把根节点入栈/队列两次。每次提取两个结点并比较它们的值（栈/队列中每两个连续的结点应该是相等的，而且它们的子树互为镜像），然后将两个结点的左右子结点按相反的顺序插入栈/队列中。当栈/队列为空时，或者我们检测到树不对称（即从栈/队列中取出两个不相等的连续结点）时，该算法结束

class Solution:
    # 栈迭代方法，如果是队列使用pop(0)
    def is_symmetric1(self, root):
        stack = [root, root]
        while stack:
            left = stack.pop()
            right = stack.pop()
            if left is None and right is None:
                continue
            if left is None or right is None or left.val != right.val:
                return False
            stack.append(left.left)
            stack.append(right.right)
            stack.append(left.right)
            stack.append(right.left)
        return True
    def is_symmetric2(self, root):
        if not root: return True
        stack = [(root.left, root.right)]
        while stack:
            left, right = stack.pop()
            if left is None and right is None:
                continue
            if left and right and left.val == right.val:
                stack.append((left.left, right.right))
                stack.append((left.right, right.left))
            else: return False
        return True
    
    
    # 利用层次搜索方法
    def is_symmetric_BFS(self, root):
        if not root: return True
        if not (root.left or root.right): return True

        stack = [root]
        while stack:
            n = len(stack)
            vals = []  #  存放每层的值
            for i in range(n):
                s = stack.pop(0)
                if s:
                    vals.append(s.val)
                    stack.append(s.left)
                    stack.append(s.right)
                else: vals.append('null')
            i = 0
            while i < (len(vals) // 2):
                if vals[i] != vals[-1-i]: return False
                i += 1
        return True

3. 测试用例

1. 功能测试:
    对称[1,2,2,3,4,4,3]
    不对称[1,2,2,'null',3,'null',3]
2. 特殊测试：
	只有一个值[2]
     空[]