Binary Tree Cameras LeetCode solution in C++

1
class Solution {
2
 public:
3
  map<TreeNode *, int> mpr;
4
  int dp[1009][3];
5
  int minCameraCover(TreeNode *root) {
6
    int num = 0;
7
    adres(root, num);
8
    memset(dp, -1, sizeof(dp));
9

10
    int t1 = dp_fun(root, 0), t2 = dp_fun(root, 1), t3 = dp_fun(root, 2);
11

12
    return min({t1, t3});
13
  }
14

15
  int dp_fun(TreeNode *cur, int st) {
16
    int nd = mpr[cur];
17
    if (dp[nd][st] == -1) {
18
      if (cur == NULL) {
19
        if (st == 2) {
20
          return 1e8;
21
        } else {
22
          return 0;
23
        }
24
      }
25
      if (st == 2) {
26
        dp[nd][st] = 1 + min({dp_fun(cur->left, 1) + dp_fun(cur->right, 1),
27
                              dp_fun(cur->left, 1) + dp_fun(cur->right, 2),
28
                              dp_fun(cur->left, 2) + dp_fun(cur->right, 1),
29
                              dp_fun(cur->left, 2) + dp_fun(cur->right, 2)});
30
      } else if (st == 1) {
31
        dp[nd][st] = min({dp_fun(cur->left, 0) + dp_fun(cur->right, 0),
32
                          dp_fun(cur->left, 0) + dp_fun(cur->right, 2),
33
                          dp_fun(cur->left, 2) + dp_fun(cur->right, 0),
34
                          dp_fun(cur->left, 2) + dp_fun(cur->right, 2)});
35
      } else {
36
        dp[nd][st] = min({dp_fun(cur, 2), dp_fun(cur->left, 2) + dp_fun(cur->right, 0),
37
                          dp_fun(cur->left, 0) + dp_fun(cur->right, 2),
38
                          dp_fun(cur->left, 2) + dp_fun(cur->right, 2)});
39
      }
40
    }
41
    return dp[nd][st];
42
  }
43

44
  void adres(TreeNode *cur, int &cnt) {
45
    if (cur == NULL) {
46
      return;
47
    }
48
    mpr[cur] = cnt;
49
    cnt++;
50

51
    adres(cur->left, cnt);
52
    adres(cur->right, cnt);
53
  }
54
};