アルゴリズムとデータ構造

この二分木は「フル」でしょうか？

与えられた二分木は「フル」(full) かどうかを判定します。フル二分木 (full binary tree) とは、すべてのノードが2つの子を持つか、まったく子を持たないかのどちらかで構成される特別な二分木のことです。「proper」二分木と呼ばれることもあります。
 
notion image

入力

入力には、二分木の各ノードの値が空白区切りの整数として与えられます。これらの値は、先に述べたように左部分木から右部分木へと順番にたどる形で並んでいます。値が 0 のとき、そのノードは存在しないことを意味します。与えられる二分木は必ず有効であると保証されています。

出力

もし二分木がフル二分木であれば Yes、そうでなければ No を出力してください。

例

入力
出力
1 2 3 4 5 0 0 0 0 6 7 0 0 8 9 0 0 0 0
Yes
1 2 3 4 5 0 0 7 8 0 0 0 0 0 6 0 0
No

解説

  1. 最初の例では、すべてのノードが子を持たないか、2つの子を持つかのいずれかしかないため、フル二分木になっています。
      2. notion image
  1. 二番目の例では、値が3のノードが1つしか子を持たないため、フル二分木ではありません。
      2. notion image

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue