Գտնել այն հանգույցների քանակը, որոնք ունեն միայն մեկ զավակ հանգույց

Բինար ծառ (Binary Tree) կառուցելը կարելի է իրականացնել ռեկուրսիվ տարբերակով։ Ենթադրենք, որ ծառը կազմում ենք օգտատիրոջ մուտքագրած թվերի հիման վրա։ Եթե հանգույցը գոյություն չունի, մուտքագրում են 0, իսկ եթե այն գոյություն ունի, մուտքագրվում է դրական թիվ։
Ելակետը վերցնելով արմատ (root) հանգույցը, մենք կարդում ենք օգտատիրոջ մուտքագրած թիվը և, եթե այն դրական է, շարունակում ենք ռեկուրսիան համապատասխան ենթածառի ուղղությամբ։ Եթե մուտքագրած թիվը 0 է, ապա այդ ուղղությամբ ծառի կառուցումը դադարվում է։
notion image
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

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

  1. Առաջին օրինակում բինար ծառը չունի որևէ հանգույց, որն ունի միայն մեկ զավակ:
    1. notion image
  1. Երկրորդ օրինակում բինար ծառում միայն մեկ հանգույց ունի մեկ զավակ, և դա 3 համար ունեցող հանգույցն է:
    1. notion image
 
Խորհուրդ 😎
Կարող եք փոփոխել վերոնշյալ կոդը, որպեսզի հանգույցներ ստեղծեք պայմանով՝ աջ կամ ձախ հանգույցը ձևավորեք միայն այն դեպքում, երբ մուտքագրված արժեքը 0-ից տարբեր է։
 

Constraints

Time limit: 3 seconds

Memory limit: 512 MB

Output limit: 1 MB

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