跳转至

LCP 64. 二叉树灯饰

题目描述

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

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

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

示例 1：

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

示例 2：

输入：root = [1,1,1,1,null,null,1]
输出：1
解释：以下是最佳的方案，如图所示

示例 3：

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

提示：

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

解法

方法一：递归

我们注意到，三个开关只能影响当前节点及其左右子节点，因此我们可以将当前节点的状态分为四种：

  • 全灭：当前节点及其左右子节点的灯均处于关闭状态；
  • 全亮：当前节点及其左右子节点的灯均处于开启状态；
  • 当前灯亮：当前节点的灯处于开启状态，其余节点的灯均处于关闭状态；
  • 当前灯灭：当前节点的灯处于关闭状态，其余节点的灯均处于开启状态；

我们用 \(t_1\), \(t_2\), \(t_3\), \(t_4\) 分别表示四种状态下，需要操作的开关次数。我们可以发现，对于当前节点的状态，我们先递归计算其左右子节点的状态 \(l_1\), \(l_2\), \(l_3\), \(l_4\) 和 \(r_1\), \(r_2\), \(r_3\), \(r_4\)，然后根据当前节点的灯的状态，可以得到四种状态下的最小操作次数：

如果当前节点的灯处于开启状态，那么：

  • 全灭 \(t_1 = min(l_1 + r_1 + 1, l_2 + r_2 + 1, l_3 + r_3 + 1, l_4 + r_4 + 3)\)
  • 全亮 \(t_2 = min(l_1 + r_1 + 2, l_2 + r_2, l_3 + r_3 + 2, l_4 + r_4 + 2)\)
  • 当前灯亮 \(t_3 = min(l_1 + r_1, l_2 + r_2 + 2, l_3 + r_3 + 2, l_4 + r_4 + 2)\)
  • 当前灯灭 \(t_4 = min(l_1 + r_1 + 1, l_2 + r_2 + 1, l_3 + r_3 + 3, l_4 + r_4 + 1)\)

如果当前节点的灯处于关闭状态，那么：

  • 全灭 \(t_1 = min(l_1 + r_1, l_2 + r_2 + 2, l_3 + r_3 + 2, l_4 + r_4 + 2)\)
  • 全亮 \(t_2 = min(l_1 + r_1 + 1, l_2 + r_2 + 1, l_3 + r_3 + 3, l_4 + r_4 + 1)\)
  • 当前灯亮 \(t_3 = min(l_1 + r_1 + 1, l_2 + r_2 + 1, l_3 + r_3 + 1, l_4 + r_4 + 3)\)
  • 当前灯灭 \(t_4 = min(l_1 + r_1 + 2, l_2 + r_2, l_3 + r_3 + 2, l_4 + r_4 + 2)\)

最后，我们返回四种状态下的最小操作次数即可。

最终答案为 \(t_1\)，因为我们需要将所有节点的灯都关闭。

时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 为二叉树的节点个数。

 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
# 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:
        def dfs(root):
            if root is None:
                return 0, 0, 0, 0
            l1, l2, l3, l4 = dfs(root.left)
            r1, r2, r3, r4 = dfs(root.right)
            t1 = t2 = t3 = t4 = inf
            if root.val:
                t1 = min(l1 + r1 + 1, l2 + r2 + 1, l3 + r3 + 1, l4 + r4 + 3)
                t2 = min(l1 + r1 + 2, l2 + r2, l3 + r3 + 2, l4 + r4 + 2)
                t3 = min(l1 + r1, l2 + r2 + 2, 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, l2 + r2 + 2, l3 + r3 + 2, l4 + r4 + 2)
                t2 = min(l1 + r1 + 1, l2 + r2 + 1, l3 + r3 + 3, l4 + r4 + 1)
                t3 = min(l1 + r1 + 1, l2 + r2 + 1, l3 + r3 + 1, l4 + r4 + 3)
                t4 = min(l1 + r1 + 2, l2 + r2, l3 + r3 + 2, l4 + r4 + 2)
            return t1, t2, t3, t4

        return dfs(root)[0]

 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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int closeLampInTree(TreeNode root) {
        return dfs(root)[0];
    }

    private int[] dfs(TreeNode root) {
        int[] ans = new int[4];
        if (root == null) {
            return ans;
        }
        int[] left = dfs(root.left);
        int[] right = dfs(root.right);
        int l1 = left[0], l2 = left[1], l3 = left[2], l4 = left[3];
        int r1 = right[0], r2 = right[1], r3 = right[2], r4 = right[3];
        if (root.val != 0) {
            ans[0] = min(l1 + r1 + 1, l2 + r2 + 1, l3 + r3 + 1, l4 + r4 + 3);
            ans[1] = min(l1 + r1 + 2, l2 + r2, l3 + r3 + 2, l4 + r4 + 2);
            ans[2] = min(l1 + r1, l2 + r2 + 2, l3 + r3 + 2, l4 + r4 + 2);
            ans[3] = min(l1 + r1 + 1, l2 + r2 + 1, l3 + r3 + 3, l4 + r4 + 1);
        } else {
            ans[0] = min(l1 + r1, l2 + r2 + 2, l3 + r3 + 2, l4 + r4 + 2);
            ans[1] = min(l1 + r1 + 1, l2 + r2 + 1, l3 + r3 + 3, l4 + r4 + 1);
            ans[2] = min(l1 + r1 + 1, l2 + r2 + 1, l3 + r3 + 1, l4 + r4 + 3);
            ans[3] = min(l1 + r1 + 2, l2 + r2, l3 + r3 + 2, l4 + r4 + 2);
        }
        return ans;
    }

    private int min(int... nums) {
        int ans = 1 << 30;
        for (int num : nums) {
            ans = Math.min(ans, num);
        }
        return ans;
    }
}

 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
/**
 * 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) {
        return dfs(root)[0];
    }

    vector<int> dfs(TreeNode* root) {
        vector<int> ans(4);
        if (!root) {
            return ans;
        }
        auto left = dfs(root->left);
        auto right = dfs(root->right);
        int l1 = left[0], l2 = left[1], l3 = left[2], l4 = left[3];
        int r1 = right[0], r2 = right[1], r3 = right[2], r4 = right[3];
        if (root->val) {
            ans[0] = min({l1 + r1 + 1, l2 + r2 + 1, l3 + r3 + 1, l4 + r4 + 3});
            ans[1] = min({l1 + r1 + 2, l2 + r2, l3 + r3 + 2, l4 + r4 + 2});
            ans[2] = min({l1 + r1, l2 + r2 + 2, l3 + r3 + 2, l4 + r4 + 2});
            ans[3] = min({l1 + r1 + 1, l2 + r2 + 1, l3 + r3 + 3, l4 + r4 + 1});
        } else {
            ans[0] = min({l1 + r1, l2 + r2 + 2, l3 + r3 + 2, l4 + r4 + 2});
            ans[1] = min({l1 + r1 + 1, l2 + r2 + 1, l3 + r3 + 3, l4 + r4 + 1});
            ans[2] = min({l1 + r1 + 1, l2 + r2 + 1, l3 + r3 + 1, l4 + r4 + 3});
            ans[3] = min({l1 + r1 + 2, l2 + r2, l3 + r3 + 2, l4 + r4 + 2});
        }
        return ans;
    }
};

 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
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func closeLampInTree(root *TreeNode) (ans int) {
    const inf = 1 << 30
    var dfs func(*TreeNode) (int, int, int, int)
    dfs = func(root *TreeNode) (int, int, int, int) {
        if root == nil {
            return 0, 0, 0, 0
        }
        l1, l2, l3, l4 := dfs(root.Left)
        r1, r2, r3, r4 := dfs(root.Right)
        t1, t2, t3, t4 := inf, inf, inf, inf
        if root.Val == 1 {
            t1 = min(l1+r1+1, l2+r2+1, l3+r3+1, l4+r4+3)
            t2 = min(l1+r1+2, l2+r2, l3+r3+2, l4+r4+2)
            t3 = min(l1+r1, l2+r2+2, 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, l2+r2+2, l3+r3+2, l4+r4+2)
            t2 = min(l1+r1+1, l2+r2+1, l3+r3+3, l4+r4+1)
            t3 = min(l1+r1+1, l2+r2+1, l3+r3+1, l4+r4+3)
            t4 = min(l1+r1+2, l2+r2, l3+r3+2, l4+r4+2)
        }
        return t1, t2, t3, t4
    }
    ans, _, _, _ = dfs(root)
    return
}

 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
46
47
48
/* public class TreeNode {
*     public var val: Int
*     public var left: TreeNode?
*     public var right: TreeNode?
*     public init(_ val: Int) {
*         self.val = val
*         self.left = nil
*         self.right = nil
*     }
* }
*/

class Solution {
    func closeLampInTree(_ root: TreeNode?) -> Int {
        return dfs(root)[0]
    }

    private func dfs(_ root: TreeNode?) -> [Int] {
        var ans = [Int](repeating: 0, count: 4)
        guard let root = root else {
            return ans
        }

        let left = dfs(root.left)
        let right = dfs(root.right)

        let l1 = left[0], l2 = left[1], l3 = left[2], l4 = left[3]
        let r1 = right[0], r2 = right[1], r3 = right[2], r4 = right[3]

        if root.val != 0 {
            ans[0] = min(l1 + r1 + 1, l2 + r2 + 1, l3 + r3 + 1, l4 + r4 + 3)
            ans[1] = min(l1 + r1 + 2, l2 + r2, l3 + r3 + 2, l4 + r4 + 2)
            ans[2] = min(l1 + r1, l2 + r2 + 2, l3 + r3 + 2, l4 + r4 + 2)
            ans[3] = min(l1 + r1 + 1, l2 + r2 + 1, l3 + r3 + 3, l4 + r4 + 1)
        } else {
            ans[0] = min(l1 + r1, l2 + r2 + 2, l3 + r3 + 2, l4 + r4 + 2)
            ans[1] = min(l1 + r1 + 1, l2 + r2 + 1, l3 + r3 + 3, l4 + r4 + 1)
            ans[2] = min(l1 + r1 + 1, l2 + r2 + 1, l3 + r3 + 1, l4 + r4 + 3)
            ans[3] = min(l1 + r1 + 2, l2 + r2, l3 + r3 + 2, l4 + r4 + 2)
        }

        return ans
    }

    private func min(_ nums: Int...) -> Int {
        return nums.min() ?? Int.max
    }
}

评论