Most_Imp_Interview_leetcode_Questions_150/DivideAndConquer/ConstructQuadTree.py at main · Ak-Rajak/Most_Imp_Interview_leetcode_Questions_150 · 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
# Question link - https://leetcode.com/problems/construct-quad-tree/submissions/1794016723/?envType=study-plan-v2&envId=top-interview-150

class Node:
    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):
        self.val = val
        self.isLeaf = isLeaf
        self.topLeft = topLeft
        self.topRight = topRight
        self.bottomLeft = bottomLeft
        self.bottomRight = bottomRight

    class Solution:
        def construct(self, grid: List[List[int]]) -> Node:
            # Reacursive function for the dfs
            # n is the current size and r , c is the current row and col
            def dfs(n , r , c):
                # Base case
                # if all the same value , initailse same
                allSame = True
                # Check all the value in the grid
                for i in range(n):
                    for j in range(n):
                        if grid[r][c] != grid[r + i][c + j]:
                            allSame = False
                            break
                if allSame:
                    return Node(grid[r][c], True)

            # Divide the node vale
            n = n // 2
            topleft = dfs(n , r , c)
            topright = dfs(n , r , c + n)
            bottomleft = dfs(n , r + n , c)
            bottomright = dfs(n , r + n , c + n)

            return Node(0 , False , topleft , topright , bottomleft , bottomright)

            # Call the function with value
            return dfs(len(grid) , 0 , 0)