LeetCode-python/problem_110.py at main · saitejamanchi/LeetCode-python · GitHub

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
"""
Problem: https://leetcode.com/problems/balanced-binary-tree/submissions/

Solution: We recursively get the height of the left and right sub-trees of each node starting from bottom to top.
We check if the difference between these height is less than or equal 1 for this to be a Balanced Binary Tree.
Otherwise, it is not.

Time Complexity: Since we're visting all the nodes of the tree once the time complexity works out to be O(n).

Space Complexity: O(1) Since we're not creating any additional data structures.


"""
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
classSolution:
isTreeBalanced=True
defisSubTreeBalanced(self, root: Optional[TreeNode]) ->int:
ifnotroot:
return0

left_height=self.isSubTreeBalanced(root.left)
right_height=self.isSubTreeBalanced(root.right)

if (abs(left_height-right_height) >1):
self.isTreeBalanced=False

returnmax(left_height, right_height) +1


defisBalanced(self, root: Optional[TreeNode]) ->bool:
tmp=self.isSubTreeBalanced(root)
returnself.isTreeBalanced
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
"""
Problem: https://leetcode.com/problems/balanced-binary-tree/submissions/

Solution: We recursively get the height of the left and right sub-trees of each node starting from bottom to top.
We check if the difference between these height is less than or equal 1 for this to be a Balanced Binary Tree.
Otherwise, it is not.

Time Complexity: Since we're visting all the nodes of the tree once the time complexity works out to be O(n).

Space Complexity: O(1) Since we're not creating any additional data structures.


"""
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
classSolution:
isTreeBalanced=True
defisSubTreeBalanced(self, root: Optional[TreeNode]) ->int:
ifnotroot:
return0

left_height=self.isSubTreeBalanced(root.left)
right_height=self.isSubTreeBalanced(root.right)

if (abs(left_height-right_height) >1):
self.isTreeBalanced=False

returnmax(left_height, right_height) +1


defisBalanced(self, root: Optional[TreeNode]) ->bool:
tmp=self.isSubTreeBalanced(root)
returnself.isTreeBalanced
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
"""
Problem: https://leetcode.com/problems/balanced-binary-tree/submissions/

Solution: We recursively get the height of the left and right sub-trees of each node starting from bottom to top.
We check if the difference between these height is less than or equal 1 for this to be a Balanced Binary Tree.
Otherwise, it is not.

Time Complexity: Since we're visting all the nodes of the tree once the time complexity works out to be O(n).

Space Complexity: O(1) Since we're not creating any additional data structures.


"""
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
classSolution:
isTreeBalanced=True
defisSubTreeBalanced(self, root: Optional[TreeNode]) ->int:
ifnotroot:
return0

left_height=self.isSubTreeBalanced(root.left)
right_height=self.isSubTreeBalanced(root.right)

if (abs(left_height-right_height) >1):
self.isTreeBalanced=False

returnmax(left_height, right_height) +1


defisBalanced(self, root: Optional[TreeNode]) ->bool:
tmp=self.isSubTreeBalanced(root)
returnself.isTreeBalanced
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
"""
Problem: https://leetcode.com/problems/balanced-binary-tree/submissions/

Solution: We recursively get the height of the left and right sub-trees of each node starting from bottom to top.
We check if the difference between these height is less than or equal 1 for this to be a Balanced Binary Tree.
Otherwise, it is not.

Time Complexity: Since we're visting all the nodes of the tree once the time complexity works out to be O(n).

Space Complexity: O(1) Since we're not creating any additional data structures.


"""
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
classSolution:
isTreeBalanced=True
defisSubTreeBalanced(self, root: Optional[TreeNode]) ->int:
ifnotroot:
return0

left_height=self.isSubTreeBalanced(root.left)
right_height=self.isSubTreeBalanced(root.right)

if (abs(left_height-right_height) >1):
self.isTreeBalanced=False

returnmax(left_height, right_height) +1


defisBalanced(self, root: Optional[TreeNode]) ->bool:
tmp=self.isSubTreeBalanced(root)
returnself.isTreeBalanced
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
"""
Problem: https://leetcode.com/problems/balanced-binary-tree/submissions/

Solution: We recursively get the height of the left and right sub-trees of each node starting from bottom to top.
We check if the difference between these height is less than or equal 1 for this to be a Balanced Binary Tree.
Otherwise, it is not.

Time Complexity: Since we're visting all the nodes of the tree once the time complexity works out to be O(n).

Space Complexity: O(1) Since we're not creating any additional data structures.


"""
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
classSolution:
isTreeBalanced=True
defisSubTreeBalanced(self, root: Optional[TreeNode]) ->int:
ifnotroot:
return0

left_height=self.isSubTreeBalanced(root.left)
right_height=self.isSubTreeBalanced(root.right)

if (abs(left_height-right_height) >1):
self.isTreeBalanced=False

returnmax(left_height, right_height) +1


defisBalanced(self, root: Optional[TreeNode]) ->bool:
tmp=self.isSubTreeBalanced(root)
returnself.isTreeBalanced
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
"""
Problem: https://leetcode.com/problems/balanced-binary-tree/submissions/

Solution: We recursively get the height of the left and right sub-trees of each node starting from bottom to top.
We check if the difference between these height is less than or equal 1 for this to be a Balanced Binary Tree.
Otherwise, it is not.

Time Complexity: Since we're visting all the nodes of the tree once the time complexity works out to be O(n).

Space Complexity: O(1) Since we're not creating any additional data structures.


"""
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
classSolution:
isTreeBalanced=True
defisSubTreeBalanced(self, root: Optional[TreeNode]) ->int:
ifnotroot:
return0

left_height=self.isSubTreeBalanced(root.left)
right_height=self.isSubTreeBalanced(root.right)

if (abs(left_height-right_height) >1):
self.isTreeBalanced=False

returnmax(left_height, right_height) +1


defisBalanced(self, root: Optional[TreeNode]) ->bool:
tmp=self.isSubTreeBalanced(root)
returnself.isTreeBalanced
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
"""
Problem: https://leetcode.com/problems/balanced-binary-tree/submissions/

Solution: We recursively get the height of the left and right sub-trees of each node starting from bottom to top.
We check if the difference between these height is less than or equal 1 for this to be a Balanced Binary Tree.
Otherwise, it is not.

Time Complexity: Since we're visting all the nodes of the tree once the time complexity works out to be O(n).

Space Complexity: O(1) Since we're not creating any additional data structures.


"""
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
classSolution:
isTreeBalanced=True
defisSubTreeBalanced(self, root: Optional[TreeNode]) ->int:
ifnotroot:
return0

left_height=self.isSubTreeBalanced(root.left)
right_height=self.isSubTreeBalanced(root.right)

if (abs(left_height-right_height) >1):
self.isTreeBalanced=False

returnmax(left_height, right_height) +1


defisBalanced(self, root: Optional[TreeNode]) ->bool:
tmp=self.isSubTreeBalanced(root)
returnself.isTreeBalanced
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
"""
Problem: https://leetcode.com/problems/balanced-binary-tree/submissions/

Solution: We recursively get the height of the left and right sub-trees of each node starting from bottom to top.
We check if the difference between these height is less than or equal 1 for this to be a Balanced Binary Tree.
Otherwise, it is not.

Time Complexity: Since we're visting all the nodes of the tree once the time complexity works out to be O(n).

Space Complexity: O(1) Since we're not creating any additional data structures.


"""
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
classSolution:
isTreeBalanced=True
defisSubTreeBalanced(self, root: Optional[TreeNode]) ->int:
ifnotroot:
return0

left_height=self.isSubTreeBalanced(root.left)
right_height=self.isSubTreeBalanced(root.right)

if (abs(left_height-right_height) >1):
self.isTreeBalanced=False

returnmax(left_height, right_height) +1


defisBalanced(self, root: Optional[TreeNode]) ->bool:
tmp=self.isSubTreeBalanced(root)
returnself.isTreeBalanced