这里是题目描述

样例 1

输入: {1,2,2,3,4,4,3} 输出: true 解释:     1    /    2   2  /  /  3  4 4  3 {1,2,2,3,4,4,3}这棵二叉树是对称的 

样例 2

输入: {1,2,2,#,3,#,3} 输出: false 解释:     1    /    2   2           3    3 很显然这棵二叉树并不对称 

用递归和迭代的方法来解决这个问题(2 种解法)

代码

··· 使用分治法 Divide Conquer 的版本 """ Definition of TreeNode: class TreeNode:     def __init__(self, val):         self.val = val         self.left, self.right = None, None """  class Solution:     """     @param root: root of the given tree     @return: whether it is a mirror of itself      """     def isSymmetric(self, root):         if not root:             return True         return self._is_symmetric(root.left, root.right)              def _is_symmetric(self, left_root, right_root):         if left_root is None and right_root is None:             return True         if left_root is None or right_root is None:             return False         if left_root.val != right_root.val:             return False                      left = self._is_symmetric(left_root.left, right_root.right)         right = self._is_symmetric(left_root.right, right_root.left)         return left and right 

使用 Iteration 的版本

""" Definition of TreeNode: class TreeNode:     def __init__(self, val):         self.val = val         self.left, self.right = None, None """  class Solution:     """     @param root: root of the given tree     @return: whether it is a mirror of itself      """          def isSymmetric(self, root):         inorder = self.inorder(root, reverse=False)         reverse_inorder = self.inorder(root, reverse=True)         if inorder != reverse_inorder:             return False                      preorder = self.preorder(root, reverse=False)         reverse_preorder = self.preorder(root, reverse=True)         return preorder == reverse_preorder              def get_left(self, node, reverse):         if reverse:             return node.right         return node.left              def get_right(self, node, reverse):         if reverse:             return node.left         return node.right              def preorder(self, root, reverse):         stack = [root]         order = []         while stack:             node = stack.pop()             order.append(node.val)             right = self.get_right(node, reverse)             if right:                 stack.append(right)             left = self.get_left(node, reverse)             if left:                 stack.append(left)         return order              def inorder(self, root, reverse):         stack = []         while root is not None:             stack.append(root)             root = self.get_left(root, reverse)                      order = []         while stack:             node = stack[-1]             order.append(node.val)             right = self.get_right(node, reverse)             if right is not None:                 node = right                 while node is not None:                     stack.append(node)                     node = self.get_left(node, reverse)             else:                 stack.pop()                 while stack and self.get_right(stack[-1], reverse) == node:                     node = stack.pop()                  return order 

使用 BFS 算法的版本

""" Definition of TreeNode: class TreeNode:     def __init__(self, val):         self.val = val         self.left, self.right = None, None """  class Solution:     """     @param root: root of the given tree     @return: whether it is a mirror of itself      """     def isSymmetric(self, root):         queue = [root]         while queue:             next_queue = []             for i in range(len(queue)):                 if queue[i] is None:                     continue                 next_queue.append(queue[i].left)                 next_queue.append(queue[i].right)             if not self.is_mirror(next_queue):                 return False             queue = next_queue         return True              def is_mirror(self, queue):         left, right = 0, len(queue) - 1         while left < right:             if not self.is_same(queue[left], queue[right]):                 return False             left, right = left + 1, right - 1         return True              def is_same(self, node1, node2):         if node1 and node2:             return node1.val == node2.val         return node1 is None and node2 is None 

大佬有話說 (0)