Ալգորիթմներ և Տվյալների Կառուցվածքներ

Արդյո՞ք բինար ծառը լրիվ է

Ձեզ խնդրում են պարզել, թե արդյոք տրված բինար ծառը լրիվ է:
Լրիվ բინար ծառ (complete binary tree) ենք համարում այն ծառը, որի բոլոր մակարդակները ամբողջովին լցված են, բացառությամբ ամենացածր մակարդակի, որտեղ հանգույցները լցված են հնարավորինս ձախից սկսած:
Վերևում示ված երկու ծառերն էլ լցված են այս սկզբունքով և համարվում են լրիվ բինար ծառեր:
notion image
notion image

Մուտք

Մուտքը պարունակում է բացատով բաժանված ամբողջ թվեր, որոնք ներկայացնում են բինար ծառի հանգույցների արժեքները: Արժեքը տրվում է այնպես, ինչպես նկարագրված էր նախորդ հայտարարությունում (յուրաքանչյուր անգամ նախաճյուղում ձախ և ապա աջ ենթառառները դիտարկելու սկզբունքով): 0 արժեքը նշանակում է, որ տվյալ հանգույցը գոյություն չունի: Ենթադրվում է, որ մուտքագրված բինար ծառը վավեր է:

Ելք

Ծրագիրը ելքում պետք է տպի Yes, եթե բինար ծառը լրիվ է, իսկ հակառակ դեպքում՝ No:

Օրինակներ

Մուտք
Ելք
1 2 3 4 5 8 9 0 0 0 0 0 0 6 7 0 0 0 0
Yes
1 2 3 4 5 8 0 0 0 0 0 6 7 0 0 0 0
Yes
1 2 3 4 5 0 0 0 0 6 7 0 0 8 9 0 0 0 0
No
1 2 3 4 5 0 0 7 8 0 0 0 0 0 6 0 0
No

Բացատրություն

  1. Օրինակ 1-ը լրիվ բինար ծառ է, քանի որ վերջին մակարդակը լցված է ձախից սկսած
      2. notion image
  1. Օրինակ 2-ը նույնպես լրիվ բինար ծառ է, քանի որ վերջին մակարդակի հանգույցները նույնպես լցված են ձախից սկսած
      2. notion image
  1. Օրինակ 3-ը լրիվ բինար ծառ չէ, քանի որ վերջին մակարդակը լցված չէ ձախից սկսած
      2. notion image
  1. Օրինակ 4-ը ևս լրիվ բինար ծառ չէ նույն պատճառով
      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