【LeetCode每天一题】Symmetric Tree(对称树)

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

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

 

But the following [1,2,2,null,3,null,3] is not:

    1
   / \
  2   2
   \   \
   3    3

思路

  这道题是让我们判断一个树是否时对称树,这道题的解法通多的,一种解法是使用广度优先办法进行对每一层的数字是否是对称的,但是这种办法比较冗余的,时间效率也比较高。另外一种就是我们直接使用递归来进行解决,每次判断每个节点的左右节点和另外一个节点的左右节点是否相等。以直到最后遍历完毕。
解决代码



 1 # Definition for a binary tree node.
 2 # class TreeNode(object):
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.left = None
 6 #         self.right = None
 7 
 8 class Solution(object):
 9     def isSymmetric(self, root):
10         """
11         :type root: TreeNode
12         :rtype: bool
13         """
14         if not root:
15             return True
16         return self.symetric(root, root)
17            
20     def symetric(self, root1, root2):
21         if not root1 and not root2:    # 两个节点都为空的话为真
22             return True
23         if not root1 or not root2:     # 其中一个为空,就是不对称的
24             return False
25         if root1.val == root2.val:   # 两个节点不为空时判断节点的值是否相等
26             return self.symetric(root1.left, root2.right) and self.symetric(root1.right, root2.left)  # 判断每个节点的左右节点和右左节点
27         return False
上一篇:对称的二叉树


下一篇:第8章 不相交集类