上次编辑到这里，代码来自缓存 点击恢复默认模板
/**
* 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 closeLampInTree(TreeNode* root) {
}
};
python3 解法, 执行用时: 440 ms, 内存消耗: 41.1 MB, 提交时间: 2023-10-25 07:47:11
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def closeLampInTree(self, root: TreeNode) -> int:
# 1:全亮 2:全灭 3:当前灯亮,其余全灭 4:当前灯灭,其余全亮
def dfs(c):
if not c:
return 0,0,0,0
l1,l2,l3,l4 = dfs(c.left)
r1,r2,r3,r4 = dfs(c.right)
if c.val:
t1 = min(l1 + r1,2 + l2 + r2,2 + l3 + r3,2 + l4 + r4)
t2 = min(1 + l2 + r2,l1 + r1 + 1,l3 + r3 + 1,l4 + r4 + 3)
t3 = min(l1 + r1 + 2,l2 + r2,l3 + r3 + 2,l4 + r4 + 2)
t4 = min(l1 + r1 + 1,l2 + r2 + 1,l3 + r3 + 3,l4 + r4 + 1)
else:
t1 = min(l1 + r1 + 1,1 + l2 + r2,3 + l3 + r3,1 + l4 + r4)
t2 = min(l2 + r2,l1 + r1 + 2,l3 + r3 + 2,l4 + r4 + 2)
t3 = min(l1 + r1 + 1,l2 + r2 + 1,l3 + r3 + 1,l4 + r4 + 3)
t4 = min(l1 + r1,l2 + r2 + 2,l3 + r3 + 2,l4 + r4 + 2)
return t1,t2,t3,t4
ans = dfs(root)
return ans[1]
cpp 解法, 执行用时: 208 ms, 内存消耗: 138.7 MB, 提交时间: 2023-10-25 07:46:47
class Solution {
tuple<int, int, int, int> dfs(TreeNode *root) {
if (root == nullptr) return {0, 0, 0, 0};
auto [la, lb, lc, ld] = dfs(root->left);
auto [ra, rb, rc, rd] = dfs(root->right);
int v = root->val;
int x = min({la + ra + (v ? 1 : 0), lb + rb + (v ? 1 : 2), lc + rc + (v ? 1 : 2), ld + rd + (v ? 3 : 2)});
int y = min({la + ra + (v ? 0 : 1), lb + rb + (v ? 2 : 1), lc + rc + (v ? 2 : 1), ld + rd + (v ? 2 : 3)});
int z = min({la + ra + (v ? 2 : 1), lb + rb + (v ? 2 : 3), lc + rc + (v ? 0 : 1), ld + rd + (v ? 2 : 1)});
int k = min({la + ra + (v ? 1 : 2), lb + rb + (v ? 3 : 2), lc + rc + (v ? 1 : 0), ld + rd + (v ? 1 : 2)});
return {x, y, z, k};
}
public:
int closeLampInTree(TreeNode *root) {
auto [x, y, z, k] = dfs(root);
return min({x, y + 1, z + 1, k + 2});
}
};
cpp 解法, 执行用时: 604 ms, 内存消耗: 386.2 MB, 提交时间: 2023-10-25 07:46:24
/**
* 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 {
const int INF = (int) 1e9;
vector<int> dp(TreeNode *node) {
if (node == nullptr) return { 0, 0, 0, 0 };
vector<int> L = dp(node->left), R = dp(node->right);
vector<int> vec = {INF, INF, INF, INF};
// 枚举以子节点为根的子树的状态，a 表示子节点的状态，b 表示除子节点外的其它节点的状态
for (int a = 0; a < 2; a++) for (int b = 0; b < 2; b++) {
int from = b * 2 + a;
int c = node->val;
// 每种操作最多做一次，因此用二进制枚举做了哪些操作
for (int i = 0; i < 8; i++) {
int x = i & 1, y = i >> 1 & 1, z = i >> 2 & 1;
// 子节点只受操作 2 和 3 的影响
int aa = (y ^ z ? 1 - a : a);
// 除子节点外的其它节点只受操作 2 的影响
int bb = (y ? 1 - b : b);
// 当前节点受所有操作影响
int cc = (x ^ y ^ z ? 1 - c : c);
// 除根外的节点要保持一致，否则后续没有操作能让它们一致
if (aa != bb) continue;
vec[aa * 2 + cc] = min(vec[aa * 2 + cc], L[from] + R[from] + x + y + z);
}
}
return vec;
}
public:
int closeLampInTree(TreeNode* root) {
return dp(root)[0];
}
};
java 解法, 执行用时: 646 ms, 内存消耗: 67 MB, 提交时间: 2023-10-25 07:46:03
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
//任意一个节点
//会受到的影响
//其祖先节点开关2 的切换次数 偶数 为 不切换 奇数为切换
//其父节点是否是否切换了开关3
HashMap<TreeNode, int[][]> map;
public int closeLampInTree(TreeNode root) {
map = new HashMap<>();
return dfs(root, false, false);
}
public int dfs(TreeNode node, boolean switch2Stat, boolean switch3Stat){
if(node == null) return 0;
int x = switch2Stat ? 1 : 0;
int y = switch3Stat ? 1 : 0;
int[][] val = new int[2][2];
if(map.containsKey(node)){
val = map.get(node);
if(val[x][y] > 0) return val[x][y];
}else{
map.put(node, val);
}
int result = 0;
//灯 开 的情况 , 对于开关 2 和 开关 3 可以相互抵消 , 最终还是 开
//灯 关 的情况 , 对于开关 2 和 开关 3 可以无法抵消 , 最终还是 开
if((node.val == 1) == (switch2Stat == switch3Stat)){
//枚举打开一个开关 或者打开三个开关的情况
int res1 = dfs(node.left, switch2Stat, false) +
dfs(node.right, switch2Stat, false) + 1;
result = res1;
int res2 = dfs(node.left, !switch2Stat, false) +
dfs(node.right, !switch2Stat, false) + 1;
result = res2 < result ? res2 : result;
int res3 = dfs(node.left, switch2Stat, true) +
dfs(node.right, switch2Stat, true) + 1;
result = res3 < result ? res3 : result;
int res123 = dfs(node.left, !switch2Stat, true) +
dfs(node.right, !switch2Stat, true) + 3;
result = result < res123 ? result : res123;
val[x][y] = result;
}else{
//枚举一个都不开 或 打开两个开关
int res0 = dfs(node.left, switch2Stat, false) +
dfs(node.right, switch2Stat, false);
result = res0;
int res12 = dfs(node.left, !switch2Stat, false) +
dfs(node.right, !switch2Stat, false) + 2;
result = res12 < result ? res12 : result;
int res13 = dfs(node.left, switch2Stat, true) +
dfs(node.right, switch2Stat, true) + 2;
result = result < res13 ? result : res13;
int res23 = dfs(node.left, !switch2Stat, true) +
dfs(node.right, !switch2Stat, true) + 2;
result = result < res23 ? result : res23;
val[x][y] = result;
}
return val[x][y];
}
}
cpp 解法, 执行用时: 596 ms, 内存消耗: 213.2 MB, 提交时间: 2023-10-25 07:45:49
/**
* 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 closeLampInTree(TreeNode* root) {
unordered_map<TreeNode*,int[2][2]> mp;//一维代表该灯是否关闭,二维代表祖先的3开关的奇偶性
int invalid_num = -1;
function<int(TreeNode*,bool,bool)> dfs = [&](TreeNode* node,bool switch2,bool switch3)
{
if(!node)return 0;
int isClose = (node->val == 0) == (switch2 == switch3);
if(mp.count(node) && mp[node][isClose][switch2] != invalid_num)
{
return mp[node][isClose][switch2];
}
int res;
if(isClose)
{
int res0 = dfs(node->left,switch2, false) + dfs(node->right,switch2, false);
int res12 = dfs(node->left,!switch2, false) + dfs(node->right,!switch2,false) + 2;
int res13 = dfs(node->left,switch2,true) + dfs(node->right,switch2,true) + 2;
int res23 = dfs(node->left,!switch2,true) + dfs(node->right,!switch2,true) + 2;
res = min(min(res0,res12),min(res23,res13));
}
else
{
int res1 = dfs(node->left,switch2, false) + dfs(node->right,switch2, false) + 1;
int res2 = dfs(node->left,!switch2, false) + dfs(node->right,!switch2,false) + 1;
int res3 = dfs(node->left,switch2,true) + dfs(node->right,switch2,true) + 1;
int res123 = dfs(node->left,!switch2,true) + dfs(node->right,!switch2,true) + 3;
res = min(min(res1,res2),min(res3,res123));
}
if(!mp.count(node))
{
memset(mp[node],-1,sizeof mp[node]);
}
mp[node][isClose][switch2] = res;
return res;
};
return dfs(root, false, false);
}
};
golang 解法, 执行用时: 488 ms, 内存消耗: 48.1 MB, 提交时间: 2023-10-25 07:45:24
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func closeLampInTree(root *TreeNode) (ans int) {
type tuple struct {
node *TreeNode
switch2, switch3 bool
}
dp := map[tuple]int{} // 记忆化搜索
var f func(*TreeNode, bool, bool) int
f = func(node *TreeNode, switch2, switch3 bool) int {
if node == nil {
return 0
}
p := tuple{node, switch2, switch3}
if res, ok := dp[p]; ok {
return res
}
if node.Val == 1 == (switch2 == switch3) { // 当前节点为开灯
res1 := f(node.Left, switch2, false) + f(node.Right, switch2, false) + 1
res2 := f(node.Left, !switch2, false) + f(node.Right, !switch2, false) + 1
res3 := f(node.Left, switch2, true) + f(node.Right, switch2, true) + 1
r123 := f(node.Left, !switch2, true) + f(node.Right, !switch2, true) + 3
dp[p] = min(res1, res2, res3, r123)
} else { // 当前节点为关灯
res0 := f(node.Left, switch2, false) + f(node.Right, switch2, false)
res12 := f(node.Left, !switch2, false) + f(node.Right, !switch2, false) + 2
res13 := f(node.Left, switch2, true) + f(node.Right, switch2, true) + 2
res23 := f(node.Left, !switch2, true) + f(node.Right, !switch2, true) + 2
dp[p] = min(res0, res12, res13, res23)
}
return dp[p]
}
return f(root, false, false)
}
func min(a, b, c, d int) int {
if b < a {
a = b
}
if c < a {
a = c
}
if d < a {
a = d
}
return a
}
python3 解法, 执行用时: 1516 ms, 内存消耗: 76.6 MB, 提交时间: 2023-10-25 07:45:08
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def closeLampInTree(self, root: TreeNode) -> int:
@cache # 记忆化搜索
def f(node: TreeNode, switch2: bool, switch3: bool) -> int:
if node is None:
return 0
if (node.val == 1) == (switch2 == switch3): # 当前节点为开灯
res1 = f(node.left, switch2, False) + f(node.right, switch2, False) + 1
res2 = f(node.left, not switch2, False) + f(node.right, not switch2, False) + 1
res3 = f(node.left, switch2, True) + f(node.right, switch2, True) + 1
res123 = f(node.left, not switch2, True) + f(node.right, not switch2, True) + 3
return min(res1, res2, res3, res123)
else: # 当前节点为关灯
res0 = f(node.left, switch2, False) + f(node.right, switch2, False)
res12 = f(node.left, not switch2, False) + f(node.right, not switch2, False) + 2
res13 = f(node.left, switch2, True) + f(node.right, switch2, True) + 2
res23 = f(node.left, not switch2, True) + f(node.right, not switch2, True) + 2
return min(res0, res12, res13, res23)
return f(root, False, False)
{:width="300px"}
{:width="300px"}