前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >2021-08-05:监控二叉树。给定一个二叉树,我们在树的节点上安装摄像头。节点上的每个摄影头都可以监视其父对象、自身及其直接

2021-08-05:监控二叉树。给定一个二叉树,我们在树的节点上安装摄像头。节点上的每个摄影头都可以监视其父对象、自身及其直接

作者头像
福大大架构师每日一题
发布2021-09-03 15:19:21
3140
发布2021-09-03 15:19:21
举报

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

福大大 答案2021-08-05:

1.递归。

X无相机,但X被覆盖。X下都被覆盖。

X有相机,但X被覆盖,X下都被覆盖。

X无相机,但X没被覆盖。X下都被覆盖。

2.贪心。

时间复杂度:O(N)。

空间复杂度:O(N)。

代码用golang编写。代码如下:

代码语言:javascript
复制
package main

import "fmt"

func main() {
    root := &TreeNode{value: 1}
    root.left = &TreeNode{value: 2}
    root.right = &TreeNode{value: 3}
    root.left.left = &TreeNode{value: 4}
    ret := minCameraCover2(root)
    fmt.Println(ret)
}

func minCameraCover2(root *TreeNode) int {
    data := process2(root)
    return data.cameras + twoSelectOne(data.status == UNCOVERED, 1, 0)
}

func twoSelectOne(c bool, a int, b int) int {
    if c {
        return a
    } else {
        return b
    }
}

type TreeNode struct {
    value int
    left  *TreeNode
    right *TreeNode
}
type Status int

const UNCOVERED = 0
const COVERED_NO_CAMERA = 1
const COVERED_HAS_CAMERA = 2

// 以x为头,x下方的节点都是被covered,得到的最优解中:
// x是什么状态,在这种状态下,需要至少几个相机
type Data struct {
    status  Status
    cameras int
}

func process2(X *TreeNode) *Data {
    if X == nil {
        return &Data{COVERED_NO_CAMERA, 0}
    }
    left := process2(X.left)
    right := process2(X.right)
    cameras := left.cameras + right.cameras

    // 左、或右,哪怕有一个没覆盖
    if left.status == UNCOVERED || right.status == UNCOVERED {
        return &Data{COVERED_HAS_CAMERA, cameras + 1}
    }

    // 左右孩子,不存在没被覆盖的情况
    if left.status == COVERED_HAS_CAMERA || right.status == COVERED_HAS_CAMERA {
        return &Data{COVERED_NO_CAMERA, cameras}
    }
    // 左右孩子,不存在没被覆盖的情况,也都没有相机
    return &Data{UNCOVERED, cameras}
}

执行结果如下:

***

[左神java代码](https://github.com/algorithmzuo/coding-for-great-offer/blob/main/src/class07/Code02_MinCameraCover.java)

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2021-08-05,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 福大大架构师每日一题 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档