建设基站

题目描述

给定一棵二叉树，每个节点代表一户居民。

你可以在树的任意节点上建设基站。一个建在节点 u 上的基站，可以覆盖节点 u 本身、u 的父节点（如果存在）以及 u 的所有直接子节点。

你的任务是，计算出最少需要建设多少个基站，才能使得树上的所有节点都被信号覆盖。

输入格式

输入为一行，包含一个或多个用空格分隔的字符串，代表一棵二叉树的层序遍历（广度优先遍历）序列。

• 正整数表示该位置有一个节点，其值为该整数。
• N 表示该位置为空节点（null）。

输出格式

输出一个整数，表示覆盖整棵树所需的最少基站数量。

样例

样例输入 1

1 2 3 4 N 5 6

样例输出 1

2

样例输入 2

1 2 N 3 N N 4

样例输出 2

2

提示

样例 1 解释

输入 1 2 3 4 N 5 6 对应如下的二叉树结构：

      1
     / \
    2   3
   /   / \
  4   5   6

一种最优的方案是在节点 2 和 5 上建设基站：

• 在节点 2 建站：覆盖 1, 2, 4。
• 在节点 5 建站：覆盖 3, 5, 6。 所有节点均被覆盖，共需 2 个基站。

样例 2 解释

输入 1 2 N 3 N N 4 对应如下的二叉树结构：

      1
     /
    2
   /
  3
 /
4

一种最优的方案是在节点 2 和 4 上建设基站。共需 2 个基站。

数据范围与约定

• 输入序列中的元素总数（包括 N）在 $$ 范围内。
• 节点值为正整数。