Tudnátok segíteni ebben a feladatban? Python

Fák bejárására keress rá. Jellemzően rekurzívan érdemes csinálni, tehát mondjuk egy függvény mindig a gyökértől indul, és annak a csomópontnak minden gyerekére meghívja önmagát, és paraméterként kapja a gyereket, mint az alatta lévő részfa gyökerét. A visszaadott érték lehet a gyerekek száma +1 (önmaga). Ezeket kell összegezni egy csomópont összes gyerekére és lehet ellenőrizni, hogy az adott csomópont alatt hány gyerek volt. Ez csak a darabszám, az összegzéshez már csak kis kiegészítés kell.

Ez most kicsit zanza lett, de talán érthető a lényeg.

Hát a feladat szerint max 10 lehet a fa mélysége, így nyugodtan lehet rekurzív megoldást alkalmazni.

Írsz két segédfüggvényt, az egyik visszaadja adott részfa méretét, a másik az elemek összegét.

Meghívod a fára az előbbit, aztán a 3 elemű részfákra az utóbbit, az összegeket pedig összeadod.

Ha nem tanultál DP-t, akkor ennyi, ha igen, akkor meg optimalizálhatsz, mert a méretek számítása ugye így exponenciális komplexitáshoz vezet, ezt lehet lineárisra javítani.

Nem kell lista. A threeSum metódus is rekurzív implementáció legyen, gondold át mik a base case-ek.

Ha null a fád, akkor nyilván 0-át kell visszaadni.

Ha nem null, akkor lekéred a méretét.

Innen 3 eset van:

- a méret pontosan 3 => lekéred az összeget és hozzá adod a válaszhoz

- a méret kisebb, mint 3 => 0 (biztosan nincs 3 elemű részfa)

- a méret nagyobb, mint 3 => rekurzívan megvizsgálod a gyerekeket