leetcode968. 监控二叉树

leetcode968. 监控二叉树

十月 29, 2020

leetcode968. 监控二叉树

给定一个二叉树，我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。

示例 1：
在这里插入图片描述
输入：[0,0,null,0,0]
输出：1
解释：如图所示，一台摄像头足以监控所有节点。

思路

设置三种状态用0,1，2表示。

  • 0表示没有被监控
  • 1表示监控器所在的位置
  • 2表示监控器监视的父节点
    后序遍历先遍历左右子树的情况，3种组合去掉重复有六种，00,11,22,01,02,12，分别对着六种情况处理。
  • 00表示当前节点左右子树都没有被监视，那当前节点肯定要监视他们，所以当前节点返回1，也就是放一个监控器
  • 01表示左右会有一个没有被监视，那么当前节点也要放一个监视器，返回1
  • 02同理，返回1
  • 11表示下面都有监视器了，当前节点肯定也被监视了，根据最开始定义返回2
  • 12也可以监视当前节点，返回2
  • 22只能推出来儿子节点被监视，当前节点不被监视，返回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
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    /*
    设置三种状态用0,1，2表示。
    - 0表示没有被监控
    - 1表示监控器所在的位置
    - 2表示监控器监视的父节点
    后序遍历先遍历左右子树的情况，3种组合去掉重复有六种，00,11,22,01,02,12，分别对着六种情况处理。
    - 00表示当前节点左右子树都没有被监视，那当前节点肯定要监视他们，所以当前节点返回1，也就是放一个监控器
    - 01表示左右会有一个没有被监视，那么当前节点也要放一个监视器，返回1
    - 02同理，返回1
    - 11表示下面都有监视器了，当前节点肯定也被监视了，根据最开始定义返回2
    - 12也可以监视当前节点，返回2
    - 22只能推出来儿子节点被监视，当前节点不被监视，返回0（如果这里再放监视器，就会再监视儿子节点，浪费）
    综上，写代码就行了
    */
    type TreeNode struct {
    	Val   int
    	Left  *TreeNode
    	Right *TreeNode
    }
    func minCameraCover(root *TreeNode) int {
    //修改原来节点的值是为了方便纠错
    	res := 0
    	if root.Left == nil && root.Right == nil {
    		return 1
    	}
    	var f func(*TreeNode) int
    	f = func(root *TreeNode) int {
    		if root == nil {
    			return 2
    		}
    		l,r := 2,2
    		l = f(root.Left)
    		r = f(root.Right)
    		//左右子树状态分析
    		if l + r == 0 || l + r == 1{
    			res++
    			root.Val = 1
    			return 1
    		} else if l == 1 && r == 1 {
    			return 2
    		} else if l + r == 3 {
    			return 2
    		} else if l + r == 4 {
    			return 0
    		} else {
    			res++
    			root.Val = 1
    			return 1
    		}

    	}
    	k :=f(root)
    	//处理根的情况
    	if k == 0 {
    		root.Val = 1
    		res++
    	}
    	return res
    }
    //层序遍历,检查结果
    func tra(root *TreeNode) {
    	queue := make([]*TreeNode,0)
    	queue = append(queue,root)
    	for len(queue) > 0 {
    		//size := len(queue)
    		nq := make([]*TreeNode,0)
    		for i,_ := range queue {
    			o := queue[i]
    			if o != nil {
    				fmt.Print(o.Val," ")
    			} else {
    				fmt.Print("nil ")
    			}

    			if o != nil {
    				nq = append(nq,o.Left)
    				nq = append(nq,o.Right)
    			}
    		}
    		queue = nq
    		fmt.Println()
    	}
    }