0%

leetcode每日一题-监控二叉树

Posted on In ,

监控二叉树

image1

对每个节点定义三种状态：

  1. 自身装了相机
  2. 自身没有装相机，但被父节点监控
  3. 自身没有装相机，但被子节点监控

每种状态的相机数都可以由左右子节点的状态得到。

1.自身装了相机

  • 左右节点没有装相机，但被父节点监控
  • 左节点装了相机，被自己监控，右节点没有装相机，被父节点监控
  • 右节点装了相机，被自己监控，左节点没有装相机，被父节点监控

2.自身没有装相机，但被父节点监控，那么左右节点不可能被父节点监控

  • 左右节点自己装了相机，被自己监控
  • 左节点装了相机，被自己监控，右节点没有装相机，但被子节点监控
  • 右节点装了相机，被自己监控，左节点没有装相机，但被子节点监控
  • 左右节点没装相机，但都被子节点监控

3.自身没有装相机，但被子节点监控，那么左右节点一定有一个装了相机，且不可能被父节点监控

  • 左右节点都装了相机，被自己监控

  • 左节点装了相机，被自己监控，右节点没有装相机，被子节点监控

  • 右节点装了相机，被自己监控，左节点没有装相机，被子节点监控

    根据上面三种情况可以写出状态转移方程，base case就是节点为空的情况，此时三种状态对应的相机数为[inf,0,0]，其中inf为一个较大的值。

1
/**
2
 * Definition for a binary tree node.
3
 * public class TreeNode {
4
 *     int val;
5
 *     TreeNode left;
6
 *     TreeNode right;
7
 *     TreeNode(int x) { val = x; }
8
 * }
9
 */
10
class Solution {
11
    //dp[0]:当前root放置了相机
12
    //dp[1]:当前root没有放置相机，但被父节点监控了
13
    //dp[2]:当前root没有放置相机，但被子节点监控了
14
    int inf = (int)1e8;
15
    public int minCameraCover(TreeNode root) {
16
        int[] dp = dfs(root);
17
        return Math.min(dp[0], dp[2]);
18
    }
19
20
    public int[] dfs(TreeNode root){
21
        if(root == null){
22
            return new int[]{inf, 0, 0};
23
        }
24
        int[] left = dfs(root.left);
25
        int[] right = dfs(root.right);
26
27
        int[] dp = new int[3];
28
        dp[0] = 1+Math.min(Math.min(left[1]+right[1], left[0]+right[1]), left[1]+right[0]);
29
        dp[1] = Math.min(Math.min(left[0]+right[0],left[0]+right[2]),Math.min(left[2]+right[0],left[2]+right[2]));
30
        dp[2] = Math.min(Math.min(left[0]+right[0], left[0]+right[2]),left[2]+right[0]);
31
        return dp;
32
    }
33
}

复杂度分析：

  • 时间复杂度：$O(N)$。
  • 空间复杂度：$O(N)$。