LeetCode/968.cpp at master · chinawch007/LeetCode · 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
class Solution {
public:
    void dp(TreeNode* p, int& yes, int&mid, int& no)
    {
        //怎么想清楚这个赋值的道理呢
        int leftYes=0, leftMid=20000, leftNo=20000, rightYes=0, rightMid=20000, rightNo=20000;

        if(!p->left && !p->right)
        {
            yes = 1;
            mid = 20000;
            no = 0;
            cout << yes << "|" << mid << "|" << no << endl;
            return;
        }

        if(p->left)
        {
            dp(p->left, leftYes, leftMid, leftNo);
            if(!p->right)
            {
                yes = min(leftYes+1, leftMid+1);
                yes = min(yes, leftNo+1);

                mid = leftYes;

                no = leftMid;
                cout << yes << "|" << mid << "|" << no << endl;
                return;
            }
        }

        if(p->right)
        {
            dp(p->right, rightYes, rightMid, rightNo);
            if(!p->left)
            {
                yes = min(rightYes+1, rightMid+1);
                yes = min(yes, rightNo+1);

                mid = rightYes;

                no = rightMid;
                cout << yes << "|" << mid << "|" << no << endl;
                return;
            }
        }

        //cout << leftYes << "|" << leftMid << "|" << leftNo << "|" << rightYes << "|" << rightMid << "|" << rightNo << "|" << endl;

        yes = min(leftYes+rightYes+1, leftYes+rightNo+1);
        yes = min(yes, leftYes+rightMid+1);
        yes = min(yes, leftMid+rightYes+1);
        yes = min(yes, leftMid+rightMid+1);
        yes = min(yes, leftMid+rightNo+1);
        yes = min(yes, leftNo+rightYes+1);
        yes = min(yes, leftNo+rightMid+1);
        yes = min(yes, leftNo+rightNo+1);

        mid = min(leftYes+rightMid, leftMid+rightYes);
        mid = min(mid, leftYes+rightYes);

        //这么写有错误啊
        no = leftMid + rightMid;

        cout << yes << "|" << mid << "|" << no << endl;

    }

    int minCameraCover(TreeNode* root) {
        int yes, mid, no;
        dp(root, yes, mid, no);
        int mi = min(yes, mid);
        return mi;
    }
};