求助大佬们救救孩子吧

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct tree {
int val;
struct tree *left;
struct tree *right;
struct tree *nei;
};
struct tree* createNode(int val) {
struct tree* newNode = (struct tree*)malloc(sizeof(struct tree));
newNode->val = val;
newNode->left = NULL;
newNode->right = NULL;
newNode->nei=NULL;
return newNode;
}
struct tree* copyTree(struct TreeNode* root) {
if (root == NULL) {
return NULL;
}
struct tree* newNode = createNode(root->val);
newNode->left = copyTree(root->left);
newNode->right = copyTree(root->right);
return newNode;
}
struct tree* fcopytree(struct tree* root) {
if (root == NULL)
return NULL;
struct tree* a = NULL; // 提前声明
if (root->val == 1) {
a = createNode(0);
} else {
a = createNode(1);
}
a->nei = root;
root->nei = a;
a->left = fcopytree(root->left);
a->right = fcopytree(root->right);
return a;
}
void s(struct tree* root){
if(root==NULL) return;
if(root->val==1) root->val=0;
else root->val=1;
}
void rs(struct tree* root){
s(root);
s(root->left);
s(root->right);
}
void fs(struct tree* root){
if(root==NULL) return;
s(root);
fs(root->left);
fs(root->right);
}
int min(int a, int b, int c) {
if (a <= b && a <= c) {
return a;
} else if (b <= a && b <= c) {
return b;
} else {
return c; // 由于只有三个数，如果前两个条件都不满足，c自然是最小的
}
}
int f(struct tree*root){
if(root==NULL) return 0;
if(root->val==0){
return f(root->left)+f(root->right);
}
else{
int x,y,z;
s(root);
x=1+f(root->left)+f(root->right);
s(root);
rs(root);
y=1+f(root->left)+f(root->right);
rs(root);
z=1+f(root->nei->left)+f(root->nei->right);
return min(x,y,z);
}
}

顶

顶

首先，证明一个结论，对于一个树形灯，无论其目标最终状态是什么，它的最优方案中，对树根的操作只有5种可能
1. 无操作
2. 1次开关1
3. 1次开关2
4. 1次开关3
5. 1次开关2 + 1次开关3
理由大约是, 1+1, 2+2, 3+3都是无意义的操作, 而1+2和1+3可以在不增加操作次数的情况下将操作向下传导, 而2+3不行
对于树中每个节点，计算该节点的子树对于4种目标状态的最短步数
1. 全0
2. 全1
3. 01型(树跟0，剩下全1)
4. 10型(树跟1，剩下全0)
自底向上计算，当计算完Left, Right的4个最短步数后，可以当前节点的4个最短步数
当前节点的val = 0时
计算全0步数和计算01型步数，是无操作和2+3的对比
计算全1步数和计算10型步数，是开关1, 开关2, 开关3的对比
当前节点val = 1时
计算全0步数和计算01型步数，是开关1, 开关2, 开关3的对比
计算全1步数和计算10型步数，是无操作和2+3的对比

供参考

对于输入[0, 0, 0, 1, 1, 1, 1]，其实只需要两步，就是对根节点执行开关2和3各一次，但按照val=0直接左右相加的想法，这个例子会得到4