[数据结构与算法]【LeetCode】二叉树的镜像和对称的二叉树

题目描述

• 剑指 Offer 27. 二叉树的镜像

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

• 剑指 Offer 28. 对称的二叉树

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

示例

• 剑指 Offer 27. 二叉树的镜像

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

• 剑指 Offer 28. 对称的二叉树

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true
示例 2：

输入：root = [1,2,2,null,3,null,3]
输出：false

方法

• 剑指 Offer 27. 二叉树的镜像

在求二叉树的镜像中，我们要做的是交换当前节点的左右子树。可以采用BFS和DFS的方法进行。

• BFS方法

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def mirrorTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if not root:
            return root
        queue = [root]
        while queue:
            r = queue.pop(0)
            r.left, r.right = r.right, r.left
            if r.left:
                queue.append(r.left)
            if r.right:
                queue.append(r.right)
        return root

• DFS方法

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def mirrorTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if not root:
            return None
        root.left, root.right = root.right, root.left
        self.mirrorTree(root.left)
        self.mirrorTree(root.right)
        return root

• 剑指 Offer 28. 对称的二叉树

在判断二叉树是否对称中，我们要做的是判断：
当前节点的左子树的左节点值是否等于当前节点的右子树的右节点值；
当前节点的左子树的右节点值是否等于当前节点的右子树的左节点值；
当前节点的左子树和和当前节点的右子树是否为空；
（注意当前节点不一定是同一节点，它是对称二叉树的对称节点）

• DFS方法

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        def mysearch(l, r):
            if not l and not r:
                return True
            if not l or not r or l.val != r.val:
                return False
            return mysearch(l.right, r.left) and mysearch(l.left, r.right)
        if not root:
            return True
        return mysearch(root.left, root.right)