leetcode_101

发表于   |   分类于

Symmetric Tree

题目戳这

题意

给定一颗二叉树，判定它是否为对称的二叉树。

解法

从题目中可以看出，对称数的定义就是根节点的左子树等于右子树，利用这个特性我们就可以写出递归和非递归两种解法。

代码

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 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 dfs(self, lt, rt):
        if not lt and not rt:
            return True
        if (lt and not rt) or (rt and not lt) or (lt.val != rt.val):
            return False # 条件不成立
        return self.dfs(lt.left,rt.right) and self.dfs(lt.right, rt.left)  # 递归判断左子树和右子树是否相等
        pass
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True
        
        return self.dfs(root.left, root.right) # 分割左右子树

非递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
import Queue
class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True
            
        q = Queue.Queue()
        q.put(root.left)
        q.put(root.right)
        
        while not q.empty():
            p1 = q.get()
            p2 = q.get()
            if not p1 and not p2:
                continue
            if not p1 or not p2:
                return False
            if p1.val != p2.val:
                return False
            q.put(p1.left)  # 分别放入左子树和右子树
            q.put(p2.right)
            
            q.put(p1.right)  #  分别放入右子树和左子树
            q.put(p2.left)
        
        return True