interview_prep/levelOrder.py at main · rishsanyal/interview_prep · 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
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
# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """

        def createLevelList(root, finalList=[]):
            if root is None:
                return finalList

            elif root.left != None and root.right != None:
                finalList.append([root.left.val, root.right.val])
                createLevelList(root.left, finalList)
                createLevelList(root.right, finalList)

            elif root.left != None:
                finalList.append([root.left.val])
                createLevelList(root.left, finalList)

            elif root.right != None:
                finalList.append([root.right.val])
                createLevelList(root.right, finalList)

            return finalList

        if root != None:
            return [[root.val]] + createLevelList(root)

        return []


    def bfs(self, root):
        if root is None:
            return []
        queue = [root]
        res = []
        while queue:
            level = []
            for _ in range(len(queue)):
                node = queue.pop(0)
                level.append(node.val)

                if node.left and node.right:
                    queue.append(node.left)
                    queue.append(node.right)
                elif node.left:
                    queue.append(node.left)
                elif node.right:
                    queue.append(node.right)
            res.append(level)
        return res

    def checkHeightBalanced(self, root):

        if root is None:
            return 0

        leftHeight = self.checkHeightBalanced(root.left)
        if leftHeight == -1:
            return -1

        rightHeight = self.checkHeightBalanced(root.right)
        if rightHeight == -1:
            return -1

        heightDiff = leftHeight - rightHeight

        if abs(heightDiff) > 1:
            return -1
        else:
            return max(leftHeight, rightHeight) + 1


# tree = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
tree = TreeNode(3, None, None)

# print(Solution().bfs(tree))

print(Solution().checkHeight(tree))