片方の子ノードだけを持つノードの数を求める
二分木は再帰的に構築することができます。ここでは、ユーザーの入力をもとに二分木を構築することを仮定します。もしノードが存在しない場合は、ユーザーからの入力は 0 となり、ノードが存在する場合は正の数が入力されます。
根ノードから始めて、ユーザー入力を読み込んでいきます。入力された値が正なら、そのサブツリーを構築し、0 の場合はそこで再帰を打ち切ります。
vals = map(int, input().split()) # 入力からBSTの値を読み込む
idx = 0 # 現在の値を指すインデックス
root = Node(vals[idx]) # ルートノードに値を設定
def read(node: Node): # 木全体のデータを再帰的に読み込む
if node.value == 0: # 現在の値が0なら => ノードは存在しない
return # そのため、左右の子ノードは読み込まない
node.left = Node(vals[idx + 1]) # 左のノードに値を設定
node.right = Node(vals[idx + 2]) # 右のノードに値を設定
idx += 2 # 現在の値のインデックスを更新
read(node.left) # 左のサブツリーのデータを読み込む
read(node.right) # 右のサブツリーのデータを読み込むここでは、あらかじめノードの数が固定されていないことに注目してください。プログラムは左側から順に入力を再帰的に読み取り、各ノードの値が 0 のときにはそこで探索を打ち切りながら進みます。そして右側に移り、同じように読み取りを継続します。すべての末端のノードが 0 となり、入力が尽きるまでこの処理は続きます。上の図のような木に対しては、ユーザーからの入力例として次のようなものが考えられます:
1 # root
2 # root.left
3 # root.right
4 # root.left.left
5 # root.left.right
0 # root.left.left.left does not exist (4の左子は存在しない)
0 # root.left.left.right does not exist (4の右子は存在しない)
0 # root.left.right.left does not exist (5の左子は存在しない)
0 # root.left.right.right does not exist (5の右子は存在しない)
6 # root.right.left
7 # root.right.right
0 # root.right.left.left does not exist (6の左子は存在しない)
0 # root.right.left.right does not exist (6の右子は存在しない)
8 # root.right.right.left
9 # root.right.right.right
0 # root.right.right.left.left does not exist (8の左子は存在しない)
0 # root.right.right.left.right does not exist (8の右子は存在しない)
0 # root.right.right.right.left does not exist (9の左子は存在しない)
0 # root.right.right.right.right does not exist (9の右子は存在しない)この入力は、配列としても表現できます。例えば
[1, 2, 3, 4, 5, 0, 0, 0, 0, 6, 7, 0, 0, 8, 9, 0, 0, 0, 0] のようにすれば、先ほどの再帰的な方法と同じ手順で二分木を構築することが可能です。有効な二分木が与えられたとき、片方の子ノードだけを持つノードがいくつあるかを求めてください。
入力
空白区切りの整数が与えられ、これらは二分木のノードの値を表します。値の並びは上記の説明と同じ規則に従います。0 は対応するノードが存在しないことを示します。
出力
片方の子ノードだけを持つ二分木のノード数を出力してください。
例
入力 | 出力 |
1 2 3 4 5 0 0 0 0 6 7 0 0 8 9 0 0 0 0 | 0 |
1 2 3 4 5 0 0 7 8 0 0 0 0 0 6 0 0 | 1 |
解説
- 最初の例では、どのノードにも片方しか子ノードが存在するケースがありません。
- 2つ目の例では、片方の子を持つノードは 3 のみです。
Pro tip 😎
上記のコードは、値が 0 かどうかを都度確認し、存在しないノードを作成しないように修正することも可能です。例えば、入力された値が 0 の場合には、そのノードを生成しないように分岐を入れるなどの工夫を加えると、より無駄のない実装にできます。
Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB