-
Notifications
You must be signed in to change notification settings - Fork 42
/
univalued-binary-tree.py
110 lines (98 loc) · 2.67 KB
/
univalued-binary-tree.py
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
# V0
# V1
# https://blog.csdn.net/fuxuemingzhu/article/details/85385974
# IDEA : BFS
# 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 isUnivalTree(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
q = collections.deque()
q.append(root)
val = root.val
while q:
node = q.popleft()
if not node:
continue
if val != node.val:
return False
q.append(node.left)
q.append(node.right)
return True
# V1'
# https://www.jianshu.com/p/fcedb4635798
class Solution:
def isUnivalTree(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
values = []
def getValues(node):
if node:
values.append(node.val)
getValues(node.left)
getValues(node.right)
getValues(root)
return len(set(values)) == 1
# V1''
# https://www.jianshu.com/p/fcedb4635798
class Solution:
def isUnivalTree(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
root_val = root.val
def hasUniValue(node):
if node:
return node.val == root_val and hasUniValue(node.left) and hasUniValue(node.right)
else:
return True
return hasUniValue(root)
# V1'''
# https://www.jianshu.com/p/fcedb4635798
def hasUniValue(node):
return not node or (node.val == root_val and hasUniValue(node.left) and hasUniValue(node.right))
# V2
# Time: O(n)
# Space: O(h)
# 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 isUnivalTree(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
s = [root]
while s:
node = s.pop()
if not node:
continue
if node.val != root.val:
return False
s.append(node.left)
s.append(node.right)
return True
# Time: O(n)
# Space: O(h)
class Solution2(object):
def isUnivalTree(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
return (not root.left or (root.left.val == root.val and self.isUnivalTree(root.left))) and \
(not root.right or (root.right.val == root.val and self.isUnivalTree(root.right)))