题目内容

给定一棵二叉树形式的居民区，树中每个实际存在的节点都住着一户居民。

现在要在某些节点上建立基站，一个建在某个节点上的基站能够覆盖该节点本身，以及所有通过边与其直接相连的邻居节点。

请你计算：为了使所有居民节点都被信号覆盖，最少需要建设多少个基站。

约束条件 节点标记序列的长度至少为 1，且不超过 3000。

输入描述

输入由若干用空白分隔的标记组成，按层序遍历顺序描述一棵二叉树。第一个标记对应根节点位置；对于每个实际存在的节点，后续标记依次表示它的左子节点和右子节点。若某个位置没有节点，则对应标记为 N。

输出描述

输出一个整数，表示使二叉树中所有实际存在的节点都被信号覆盖所需建设的最少基站数量。

样例1

输入

7

输出

1

说明

树中只有一个实际存在的居民节点 7。基站只能建在实际存在的节点上，因此必须在该节点上建 1 个基站，覆盖该节点本身，最少数量为 1。

样例2

输入

1 2 3

输出

1

说明

树包含根节点 1 及其左孩子 2、右孩子 3。在根节点 1 上建设 1 个基站，可以覆盖节点 1、2、3，因此最少需要 1 个基站。

样例3

输入

1 2 3 4 5 6 7 N N N N 8 N N 9

输出

3

说明

一种最优的建设方法如图：

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