Problem 1

判断是否是镜像二叉树
考察点：二叉树的遍历
Description:

image.png

(1)自己的解法:
镜像二叉树的两种不同的遍历:先遍历左子树和先遍历右子树，遍历的顺序结果是一样的，代码如下:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        p_l=[]
        p_r=[]
        def midTraverse(root):

            if root == None:
                p_l.append('null')
                return
            p_l.append(root.val)
            midTraverse(root.left)
            midTraverse(root.right)

        def afterTraverse(root):
            if root == None:
                p_r.append('null')
                return
            p_r.append(root.val)
            afterTraverse(root.right)
            afterTraverse(root.left)
        
        midTraverse(root)
        afterTraverse(root)
        print(p_l)
        print(p_r)
        return p_l==p_r 

这个方法的时间复杂度有点高，需要两次遍历。
(2)参考的网上的代码：
思路递归的比较树的左子树和右子树是否相似，代码如下:

class Solution:
  def isSymmetric(self, root):
    if root is None:
      return True
    else:
      return self.isMirror(root.left, root.right)

  def isMirror(self, left, right):
    if left is None and right is None:
      return True
    if left is None or right is None:
      return False

    if left.val == right.val:
      outPair = self.isMirror(left.left, right.right)
      inPiar = self.isMirror(left.right, right.left)
      return outPair and inPiar
    else:
      return False

Problem 2

翻转二叉树
Description

image.png

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if root == None:
            return
        queue = []
        queue_r=[]
        queue.append(root)
        p=TreeNode(root.val)
        queue_r.append(p)
        q=p
        while queue:
            now_node = queue.pop(0)
            p=queue_r.pop(0)
            if now_node.right != None:
                queue.append(now_node.right)
                p.left=TreeNode(now_node.right.val)
                queue_r.append(p.left)
            if now_node.left != None:
                queue.append(now_node.left)
                p.right=TreeNode(now_node.left.val)
                queue_r.append(p.right)
        return q

这个方法的空间复杂度有点高，每次都会开辟一个新的节点，参考网上其他的解法代码如下，其中

 node.left, node.right = node.right, node.left

这条代码表示并发执行

# BFS
def invertTree2(self, root):
    queue = collections.deque([(root)])
    while queue:
        node = queue.popleft()
        if node:
            node.left, node.right = node.right, node.left
            #此时node.left和node.right已经调换过来了
            queue.append(node.left)
            queue.append(node.right)
    return root