貪心算法，二叉樹(shù)與貪心的結(jié)合，有點(diǎn)難...... LeetCode:968.監(jiān)督
這題好難?。ㄗ⑨尠妫x謝Carl，講的很清晰！
class Solution {
public:
? ? int result = 0;
? ? // 0：無(wú)覆蓋， 1：有攝像頭，2：有覆蓋
? ? int inordered(TreeNode* cur) {
? ? ? ? if (!cur) return 2; // null節(jié)點(diǎn)表示有覆蓋， 為的是讓葉子節(jié)點(diǎn)的父節(jié)點(diǎn)有攝像頭
? ? ? ? int left = inordered(cur->left);
? ? ? ? int right = inordered(cur->right);
? ? ? ? // 1.如果左節(jié)點(diǎn)和右節(jié)點(diǎn)都有覆蓋，則父節(jié)點(diǎn)設(shè)為無(wú)覆蓋，這樣父節(jié)點(diǎn)的父節(jié)點(diǎn)可以設(shè)為有攝像頭
? ? ? ? if (left == 2 && right == 2) return 0;
? ? ? ? // 2.如果左右節(jié)點(diǎn)至少有一個(gè)為無(wú)覆蓋，則父節(jié)點(diǎn)設(shè)置為有攝像頭
? ? ? ? if (left == 0 || right == 0) {
? ? ? ? ? ? result++;
? ? ? ? ? ? return 1;
? ? ? ? }
? ? ? ? // 3.如果左右節(jié)點(diǎn)至少有一個(gè)為有攝像頭，則父節(jié)點(diǎn)設(shè)置為有覆蓋（注意：必須先寫(xiě)條件2，再寫(xiě)條件3 -> 可化一棵樹(shù)模擬！
? ? ? ? if (left == 1 || right == 1) return 2;
? ? ? ? return -1; // 保證編譯正常，不會(huì)運(yùn)行到這一步
? ? }
? ? int minCameraCover(TreeNode* root) {
? ? ? ? if (inordered(root) == 0) result++; // 4. 根節(jié)點(diǎn)無(wú)覆蓋時(shí)，攝像頭+1
? ? ? ? return result;
? ? }
};
