题面描述

给定一棵 二叉树，树上每个节点代表一户居民。需要在若干节点上建设基站，每个基站可以覆盖其所在节点及与其相邻的左右子节点和父节点，覆盖距离为 $1$。求覆盖整棵树的最少基站数量。

思路

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

• $f[u][0]$：在节点 $u$ 放置基站，覆盖整棵子树所需的最少基站数。

题目内容

有一棵二叉树，每个节点上都住了一户居民。现在要给这棵树上的居民建设基站，每个基站只能覆盖她所在与相邻的节点，请问信号覆盖这棵树最少需要建设多少个基站

输入描述

一个整数数组$nums(1<=num.length<=3000)$，用空格分隔，表示二叉树的节点值，正整数表示存在节点，$N$表示不存在节点，如$[1\ 2\ 3\ 4\ N\ 5\ 6]$表示一颗如下所示的树，最少需要建设$2$个基站

输出描述

最少需要建设的基站个数

样例1

输入

1 2 3 4 N 5 6

输出

2

说明

如图,$2$个基站可以覆盖所有节点

样例2

输入

1 2 N 3 N N 4

输出

2

说明

如图,$2$个基站可以覆盖所有节点(左右两种方案都能覆盖所有的节点)

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