给定一棵 二叉树,树上每个节点代表一户居民。需要在若干节点上建设基站,每个基站可以覆盖其所在节点及与其相邻的左右子节点和父节点,覆盖距离为 1。求覆盖整棵树的最少基站数量。
对每个节点 u,定义三种状态:
有一棵二叉树,每个节点上都住了一户居民。现在要给这棵树上的居民建设基站,每个基站只能覆盖她所在与相邻的节点,请问信号覆盖这棵树最少需要建设多少个基站
一个整数数组nums(1<=num.length<=3000),用空格分隔,表示二叉树的节点值,正整数表示存在节点,N表示不存在节点,如[1 2 3 4 N 5 6]表示一颗如下所示的树,最少需要建设2个基站
最少需要建设的基站个数
输入
1 2 3 4 N 5 6
输出
2
如图,2个基站可以覆盖所有节点
输入
1 2 N 3 N N 4
输出
2
如图,2个基站可以覆盖所有节点(左右两种方案都能覆盖所有的节点)