-
Notifications
You must be signed in to change notification settings - Fork 6
Expand file tree
/
Copy path101_Symmetric Tree.py
More file actions
123 lines (103 loc) · 3.87 KB
/
101_Symmetric Tree.py
File metadata and controls
123 lines (103 loc) · 3.87 KB
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
# -*- coding: utf-8 -*-
"""
Created on Wed Sep 4 15:25:36 2019
@author: leiya
"""
'''
updated 0626
0726:isSame 返回的是bool类型，如果直接写一个isSame(),是没有返回值的，需要写成return isSame()
'''
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
def dfs(left,right):
if not left and not right:
return True
if left and right and left.val == right.val:
return dfs(left.left,right.right) and dfs(left.right,right.left)
else:
return False
if not root:
return True
return dfs(root.left,root.right)
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
def isSame(left,right):
if not left and not right:
return True
if not left and right or not right and left:
return False
if left.val == right.val:
return isSame(left.left,right.right) and isSame(left.right,right.left)
else:
return False
if not root:
return True
return isSame(root.left,root.right)
#迭代版，实际上就是在bfs弹出nodes的时候进行判断
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
queue = []
queue.append((root, root))
while queue:
left, right = queue.pop(0)
if not left and not right:
continue
if not left or not right:
return False
if left.val != right.val:
return False
queue.append((left.left, right.right))
queue.append((left.right, right.left))
return True
#------------------------------------------------------------------------------
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
if root is None:
return True
def isSym(L, R):
if L is None and R is None:
return True
if L and R:
return L.val == R.val and isSym(L.left, R.right) and isSym(L.right, R.left)
else:
return False
#此处必须加一个return,如果不加return的话即使isSym有return值也不会作为isSymmetric的return返回出去
return isSym(root, root)
class Solution:
def isSymmetric(self, root):
def isSym(L,R):
if L and R:
return L.val == R.val and isSym(L.left, R.right) and isSym(L.right, R.left)
else:
return L == R
return isSym(root, root)
''' def isSymmetric(self, root):
def isSym(L,R):
if not L and not R: return True
if L and R and L.val == R.val:
return isSym(L.left, R.right) and isSym(L.right, R.left)
return False
return isSym(root, root)'''
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
if root is None:
return True
else:
return self.isSymmetric_twovariable(root.left,root.right)
def isSymmetric_twovariable(self,left,right):
if left and right:
return left.val == right.val and self.isSymmetric_twovariable(left.left,right.right) and self.isSymmetric_twovariable(left.right,right.left)
else:
return left == right
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
if root is None:
return True
return self.isSymmetricRecu(root.left,root.right)
def isSymmetricRecu(self,left,right):
if left is None and right is None:
return True
if left is not None and right is not None:
return left.val == right.val and self.isSymmetricRecu(left.left,right.right) and self.isSymmetricRecu(left.right,right.left)
else:
return False