aboutsummaryrefslogtreecommitdiff
path: root/construct_quad_tree.cpp
blob: 845cefeb40aede1f2c9c1c00dbc1e92906447103 (plain)
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
// 427. Construct Quad Tree
#include <bits/stdc++.h>
using namespace std;
#define vvd(data) vector<vector<data>>

/*
 * wtf this is right pants for a medium
 */

class Node {
public:
  bool val;
  bool isLeaf;
  Node *topLeft;
  Node *topRight;
  Node *bottomLeft;
  Node *bottomRight;
  Node() {
    val = false;
    isLeaf = false;
    topLeft = NULL;
    topRight = NULL;
    bottomLeft = NULL;
    bottomRight = NULL;
  }
  Node(bool _val, bool _isLeaf) {
    val = _val;
    isLeaf = _isLeaf;
    topLeft = NULL;
    topRight = NULL;
    bottomLeft = NULL;
    bottomRight = NULL;
  }
  Node(bool _val, bool _isLeaf, Node *_topLeft, Node *_topRight,
       Node *_bottomLeft, Node *_bottomRight) {
    val = _val;
    isLeaf = _isLeaf;
    topLeft = _topLeft;
    topRight = _topRight;
    bottomLeft = _bottomLeft;
    bottomRight = _bottomRight;
  }
};

class Solution {
public:
  Node *construct(vvd & grid) {
    grid_v = move(grid);
    leafNodes_a[0] = new Node(false, true, nullptr, nullptr, nullptr, nullptr);
    leafNodes_a[1] = new Node(true, true, nullptr, nullptr, nullptr, nullptr);
    return construct(0, 0, grid_v.size());
  }

private:
  vvd grid_v;
  array<Node *, 2> leafNodes_a;
  Node *construct(int r, int c, int s) {
    if (s == 1)
      return leafNodes_a[grid_v[r][c]];
    s /= 2;
    Node *tl = construct(r, c, s);
    Node *tr = construct(r, c + s, s);
    Node *bl = construct(r + s, c, s);
    Node *br = construct(r + s, c + s, s);
    if (tl == tr && tl == bl && tl == br)
      return tl;
    return new Node(false, false, tl, tr, bl, br);
  }
};

int main() {
  Solution obj;
  vvd grid = {{0, 1}, {1, 0}};
  cout << obj.construct(grid); // expect: [[0,1],[1,0],[1,1],[1,1],[1,0]]
}