Algorithm/test.cpp at main · yinshi197/Algorithm · 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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <string>
#include <list>
using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left = nullptr;
    TreeNode *right = nullptr;

    TreeNode() : val(0) {}
    TreeNode(int val)  : val(val) {}
    TreeNode(int val, TreeNode *left, TreeNode *right) : val(val), left(left), right(right) {}
};

class Solution {
public:
    int ret;

    int traversal(TreeNode* root)
    {
        //0：无覆盖
        //1: 有摄像头
        //2: 有覆盖
        if(root == nullptr) return 2;

        int left = traversal(root->left);
        int right = traversal(root->right);

        if(left == 2 &&  right == 2) return 0;
        if(left == 0 || right == 0)
        {
            ret++;
            return 1;
        }

        if(left == 1 || right == 1) return 2;

        return -1;
    }

    int minCameraCover(TreeNode* root) {
        ret = 0;
        //遍历结束头节点没有覆盖
        if(traversal(root) == 0) ret++;

        return ret;
    }
};

TreeNode* createTree(const std::vector<int*>& nodes)
{
    if (nodes.empty() || nodes[0] == nullptr) return nullptr;

    TreeNode* root = new TreeNode(*nodes[0]);
    std::queue<TreeNode*> q;
    q.push(root);

    int i = 1;
    while (!q.empty() && i < nodes.size())
    {
        TreeNode* current = q.front();
        q.pop();

        if (nodes[i] != nullptr)
        {
            current->left = new TreeNode(*nodes[i]);
            q.push(current->left);
        }
        i++;

        if (i < nodes.size() && nodes[i] != nullptr)
        {
            current->right = new TreeNode(*nodes[i]);
            q.push(current->right);
        }
        i++;
    }

    return root;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    vector<int*> test;
    string ch;
    while(cin >> ch)
    {
        if(ch == "q") break;
        if(ch == "#" || ch == "null" || ch == "nullptr" || ch == "NULL")
        {
            test.push_back(nullptr);
        }
        else test.push_back(new int(stoi(ch)));
    }

    TreeNode *root = createTree(test);

    Solution *so = new Solution();
    int ret = so->minCameraCover(root);
    cout << ret << endl;

    return 0;
}