题目描述

假设村落以二叉树的形状分布，我们需要选择在哪些村落建设基站。如果某个村落建设了基站，那么它和它相邻的村落（包括本节点、父节点和子节点）都会有信号覆盖。

计算出最少需要建设的基站数。

该题是$leetcode$原题:https://leetcode.cn/problems/binary-tree-cameras/solutions/422860/jian-kong-er-cha-shu-by-leetcode-solution/

思路：树上动态规划

题目内容

假设村落二叉树形状分布，我们要选择在哪些村落建设基站。如果某个村落建设了基站，那么它和它相邻的村落(本节点、父节点，子节点)也会有信号覆盖。

计算出最少需要建设的基站数。

输入描述

使用完全二叉树的数组形式表示，从左到右，从上到下遍历，$1$表示节点存在，$0$表示节点不存在。

• $1<=$节点数范围$<=8191$
• $1$表示节点存在，$0$表示节点不存在。。

输出描述

基站个数

样例1

输入

1 1 1 1 0 1 1		

输出

2

说明

最少需要$2$个基站才能覆盖所有村落

样例2

输入

1 1 0 1 0 0 0

输出

1

说明

只需要$1$个基站就能覆盖所有村落

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写