Construct Quad Tree LeetCode solution in Java

1
/*
2
// Definition for a QuadTree node.
3
class Node {
4
    public boolean val;
5
    public boolean isLeaf;
6
    public Node topLeft;
7
    public Node topRight;
8
    public Node bottomLeft;
9
    public Node bottomRight;
10

11

12
    public Node() {
13
        this.val = false;
14
        this.isLeaf = false;
15
        this.topLeft = null;
16
        this.topRight = null;
17
        this.bottomLeft = null;
18
        this.bottomRight = null;
19
    }
20

21
    public Node(boolean val, boolean isLeaf) {
22
        this.val = val;
23
        this.isLeaf = isLeaf;
24
        this.topLeft = null;
25
        this.topRight = null;
26
        this.bottomLeft = null;
27
        this.bottomRight = null;
28
    }
29

30
    public Node(boolean val, boolean isLeaf, Node topLeft, Node topRight, Node bottomLeft, Node bottomRight) {
31
        this.val = val;
32
        this.isLeaf = isLeaf;
33
        this.topLeft = topLeft;
34
        this.topRight = topRight;
35
        this.bottomLeft = bottomLeft;
36
        this.bottomRight = bottomRight;
37
    }
38
};
39
*/
40

41
class Solution {
42
  public Node construct(int[][] grid) {
43
    return helper(grid, 0, grid.length - 1, 0, grid.length - 1);
44
  }
45

46
  Node helper(int[][] grid, int l, int r, int t, int b) {
47
    if (l == r) {
48
      if (grid[t][l] == 1) return new Node(true, true);
49
      else return new Node(false, true);
50
    }
51
    if (allOnes(grid, l, r, t, b)) {
52
      Node res = new Node(true, true);
53
      return res;
54
    }
55
    if (allZeros(grid, l, r, t, b)) {
56
      Node res = new Node(false, true);
57
      return res;
58
    }
59
    Node tl = helper(grid, l, (l + r) / 2, t, (t + b) / 2);
60
    Node tr = helper(grid, ((l + r + 1) / 2), r, t, (t + b) / 2);
61
    Node bl = helper(grid, l, (l + r) / 2, (t + b + 1) / 2, b);
62
    Node br = helper(grid, ((l + r + 1) / 2), r, (t + b + 1) / 2, b);
63
    return new Node(true, false, tl, tr, bl, br);
64
  }
65

66
  boolean allOnes(int[][] grid, int l, int r, int t, int b) {
67
    // System.out.println(l+" "+r+" "+t+" "+b);
68
    for (int i = t; i <= b; i++) {
69
      for (int j = l; j <= r; j++) {
70
        if (grid[i][j] != 1) {
71
          return false;
72
        }
73
      }
74
    }
75

76
    return true;
77
  }
78

79
  boolean allZeros(int[][] grid, int l, int r, int t, int b) {
80
    for (int i = t; i <= b; i++) {
81
      for (int j = l; j <= r; j++) {
82
        if (grid[i][j] != 0) return false;
83
      }
84
    }
85
    return true;
86
  }
87
}