Գտնել այն հանգույցների քանակը, որոնք ունեն միայն մեկ զավակ հանգույց
Բինար ծառ (Binary Tree) կառուցելը կարելի է իրականացնել ռեկուրսիվ տարբերակով։ Ենթադրենք, որ ծառը կազմում ենք օգտատիրոջ մուտքագրած թվերի հիման վրա։ Եթե հանգույցը գոյություն չունի, մուտքագրում են 0, իսկ եթե այն գոյություն ունի, մուտքագրվում է դրական թիվ։
Ելակետը վերցնելով արմատ (root) հանգույցը, մենք կարդում ենք օգտատիրոջ մուտքագրած թիվը և, եթե այն դրական է, շարունակում ենք ռեկուրսիան համապատասխան ենթածառի ուղղությամբ։ Եթե մուտքագրած թիվը 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 գոյություն չունի (4-ի ձախ զավակը չկա)
0 # root.left.left.right գոյություն չունի (4-ի աջ զավակը չկա)
0 # root.left.right.left գոյություն չունի (5-ի ձախ զավակը չկա)
0 # root.left.right.right գոյություն չունի (5-ի աջ զավակը չկա)
6 # root.right.left
7 # root.right.right
0 # root.right.left.left գոյություն չունի (6-ի ձախ զավակը չկա)
0 # root.right.left.right գոյություն չունի (6-ի աջ զավակը չկա)
8 # root.right.right.left
9 # root.right.right.right
0 # root.right.right.left.left գոյություն չունի (8-ի ձախ զավակը չկա)
0 # root.right.right.left.right գոյություն չունի (8-ի աջ զավակը չկա)
0 # root.right.right.right.left գոյություն չունի (9-ի ձախ զավակը չկա)
0 # root.right.right.right.right գոյություն չունի(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
Բացատրություն
Առաջին օրինակում բինար ծառը չունի որևէ հանգույց, որն ունի միայն մեկ զավակ:
Երկրորդ օրինակում բինար ծառում միայն մեկ հանգույց ունի մեկ զավակ, և դա 3 համար ունեցող հանգույցն է:
Խորհուրդ 😎
Կարող եք փոփոխել վերոնշյալ կոդը, որպեսզի հանգույցներ ստեղծեք պայմանով՝ աջ կամ ձախ հանգույցը ձևավորեք միայն այն դեպքում, երբ մուտքագրված արժեքը 0-ից տարբեր է։