LCP 64-二叉树灯饰

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:27 2023-09-13 16:06:27 Updated    

「力扣嘉年华」的中心广场放置了一个巨型的二叉树形状的装饰树。每个节点上均有一盏灯和三个开关。节点值为 0 表示灯处于「关闭」状态，节点值为 1
表示灯处于「开启」状态。每个节点上的三个开关各自功能如下：

  • 开关 1：切换当前节点的灯的状态；
  • 开关 2：切换 以当前节点为根 的子树中，所有节点上的灯的状态；
  • 开关 3：切换 当前节点及其左右子节点 （若存在的话） 上的灯的状态；

给定该装饰的初始状态 root，请返回最少需要操作多少次开关，可以关闭所有节点的灯。

示例 1：

**输入：** root = [1,1,0,null,null,null,1]
**输出：** 2
**解释：** 以下是最佳的方案之一，如图所示
![](https://pic.leetcode-cn.com/1629357030-GSbzpY-b71b95bf405e3b223e00b2820a062ba4.gif)

示例 2：

**输入：** root = [1,1,1,1,null,null,1]
**输出：** 1
**解释：** 以下是最佳的方案，如图所示
![](https://pic.leetcode-cn.com/1629356950-HZsKZC-a4091b6448a0089b4d9e8f0390ff9ac6.gif)

示例 3：

**输入：** root = [0,null,0]
**输出：** 0
**解释：** 无需操作开关，当前所有节点上的灯均已关闭

提示：

  • 1 <= 节点个数 <= 10^5
  • 0 <= Node.val <= 1

个人赛五道题目的 视频讲解 已出炉，欢迎点赞三连，在评论区分享你对这场比赛的看法~

定义状态 (当前节点，祖先节点开关 2 的切换次数的奇偶性，父节点是否切换了开关 3)，每个状态表示从当前状态出发，最少需要操作多少次开关，可以关闭子树所有节点的灯。

跑一个树形 DP。如果当前受到祖先节点的开关影响后，变成开灯状态，那么可以操作一个或三个开关：

  • 操作开关 1；
  • 操作开关 2；
  • 操作开关 3；
  • 操作开关 123；
  • 这四种操作取最小值。

如果变成关灯状态，那么可以操作零个或两个开关：

  • 不操作任何一个开关；
  • 操作开关 12；
  • 操作开关 13；
  • 操作开关 23；
  • 这四种操作取最小值。
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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)
[sol1-Go]
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
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
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 为二叉树的节点个数。
  • 空间复杂度：O(n)。
 Comments
On this page
LCP 64-二叉树灯饰