-
Notifications
You must be signed in to change notification settings - Fork 0
/
93_Balanced_Binary_Tree.py
63 lines (50 loc) · 1.81 KB
/
93_Balanced_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
__author__ = "Wangdu Lin"
__copyright__ = "Copyright 2018, The Algorithm Project"
__credits__ = ["Wangdu Lin, jiuzhang"]
__license__ = "GPL"
__version__ = "1.0.1"
__maintainer__ = "Wangdu Lin"
__email__ = "[email protected]"
__status__ = "Production"
"""
Time: O(n)
Space: O(h), h is height of binary tree
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
@param: root: The root of binary tree.
@return: True if this Binary tree is Balanced, or false.
"""
# Solution 1: Not recommand, because single return value with multiple meaning.
# def isBalanced(self, root):
# if self.getHeight(root) >= 0:
# return True
# else:
# return False
# def getHeight(self, root):
# if root is None:
# return 0
# else:
# left_height, right_height = self.getHeight(root.left), self.getHeight(root.right)
# if left_height < 0 or right_height < 0 or abs(left_height - right_height) > 1:
# return -1
# return max(left_height, right_height) + 1
# Solution 2: Recommand, because tuple is more clear to express the algorithm logic.
def isBalanced(self, root):
result, _ = self.validate(root)
return result
def validate(self, root):
if root is None:
return True, 0
left_balan, left_height = self.validate(root.left)
if not left_balan:
return False, 0
right_balan, right_height = self.validate(root.right)
if not right_balan:
return False, 0
return abs(left_height - right_height) <= 1, max(left_height, right_height) + 1