题目链接

点我(^_^)

题意

注意，这里一个灯可以按多次。

比如 示例1：
输入：root = [1,1,0,null,null,null,1]
输出：2
解释：以下是最佳的方案之一，如同所示

解题思路

从题目的条件中可以看出有两个关键点。

• 一是从开关功能可以看出，当前节点灯的状态只受到节点自身，以及其祖先节点开关的影响，而不会受到其子孙节点开关的影响。
• 二是对于一个方案，其按开关的顺序没有影响(即只要按了这些开关即可)，且一个开关最多按一次，因为按两次就相当于回到按0次的状态了。

所以，根据这两个关键点，我们可以从根节点开始向下深度优先搜索，对于一个点，一共有八种情况(两个大类)：

• 第一类：当前节点是原本开着的，且其祖先节点的 开关2 次数的奇偶性与其父节点 开关1 次数的奇偶性相等。或者当前节点原本是关着的，且其祖先节点的 开关2 次数的奇偶性与其父节点 开关1 次数的奇偶性不相等。那么此时当前节点的灯是 开的。那么一共有四种操作(奇数次操作保证灯是关的)：

int res1 = dfs(root->left, switch2, 0) + dfs(root->right, switch2, 0) + 1; // 只按1
int res2 = dfs(root->left, !switch2, 0) + dfs(root->right, !switch2, 0) + 1; // 只按2
int res3 = dfs(root->left, switch2, 1) + dfs(root->right, switch2, 1) + 1; // 只按3
int res123 = dfs(root->left, !switch2, 1) + dfs(root->right, !switch2, 1) + 3; // 按123

• 第二类：即第一类的反状态，此时当前节点的灯是 关的。那么一共有四种操作(偶数次操作保证灯是关的)：

int res0 = dfs(root->left, switch2, 0) + dfs(root->right, switch2, 0); // 不按
int res12 = dfs(root->left, !switch2, 0) + dfs(root->right, !switch2, 0) + 2; // 按12
int res13 = dfs(root->left, switch2, 1) + dfs(root->right, switch2, 1) + 2; // 按13
int res23 = dfs(root->left, !switch2, 1) + dfs(root->right, !switch2, 1) + 2; // 按23

最后选择一个最小的即可。但是这样肯定会超时，因为有很多情况是被重复搜索的，所以我们可以采用记忆化搜索，用 dp[i][j] 表示第 i 个节点，处于 j 状态情况下按开关的总数，这里的 j = switch2<<1|switch3。

代码(C++)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int dp[100005][4];
    unordered_map<TreeNode*, int> mp;
    int dfs(TreeNode* root, int switch2, int switch3) {
        if(root == nullptr)
            return 0;
        if(dp[mp[root]][switch2<<1|switch3] != -1)
            return dp[mp[root]][switch2<<1|switch3]; 
        // 灯还是开
        if( (root->val == 1) == (switch2 == switch3) ) {
            int res1 = dfs(root->left, switch2, 0) + dfs(root->right, switch2, 0) + 1; // 只按1
            int res2 = dfs(root->left, !switch2, 0) + dfs(root->right, !switch2, 0) + 1; // 只按2
            int res3 = dfs(root->left, switch2, 1) + dfs(root->right, switch2, 1) + 1; // 只按3
            int res123 = dfs(root->left, !switch2, 1) + dfs(root->right, !switch2, 1) + 3; // 按123
            dp[mp[root]][switch2<<1|switch3] = min(min(res1, res2), min(res3, res123));
        } else { // 灯已经是关的
            int res0 = dfs(root->left, switch2, 0) + dfs(root->right, switch2, 0); // 不按
            int res12 = dfs(root->left, !switch2, 0) + dfs(root->right, !switch2, 0) + 2; // 按12
            int res13 = dfs(root->left, switch2, 1) + dfs(root->right, switch2, 1) + 2; // 按13
            int res23 = dfs(root->left, !switch2, 1) + dfs(root->right, !switch2, 1) + 2; // 按23
            dp[mp[root]][switch2<<1|switch3] = min(min(res0, res12), min(res13, res23));
        }
        return dp[mp[root]][switch2<<1|switch3];
    }
    int closeLampInTree(TreeNode* root) {
        for(int i=0; i<=100000; ++i)
            for(int j=0; j<4; ++j)
                dp[i][j] = -1;
        queue<TreeNode*> q;
        q.push(root);
        int idx = 0;
        while(!q.empty()) {
            TreeNode* temp = q.front();
            mp[temp] = idx++;
            q.pop();
            if(temp->left != nullptr)
                q.push(temp->left);
            if(temp->right != nullptr)
                q.push(temp->right);
        }
        return dfs(root, 0, 0);
    }
};