Interjúfeladat megoldás?
Adott egy függvény aminek bemenete egy bináris fa gyökere és vissza kell adni a fában a belső csomópontok értékének összegét.
A belső csomópont definíciója:
- felette van legalább egy szint
- alatta van legalább egy szint
- ugyanazon a szinten tőle balra van legalább egy csomópont
- ugyanazon a szinten tőle jobbra van legalább egy csomópont
A következő fa esetében pl. 6 lenne az eredmény:
Ezt kaptam ma interjún de nem tudtam megoldani a megadott idő alatt. A céget nem szeretném elmondani.
A nyelvet én választhattam (Java-ban próbálkoztam).
Gyakorlatilag a következő függvény törzsét kellett volna megírnom:
int innerNodeSum(BinaryTreeNode root) { ... }
A BinaryTreeNode osztálynak 3 adattagja van, left, right és value.
Annyit mondtak hogy az összeg biztosan belefér egy 32 bites intbe.
Úgy indultam el hogy elkezdem rekurzívan bejárni a fát és egy mapben/dictionaryben tárolom a szülő-gyerek kapcsolatokat de eléggé belegabalyodtam, meg nem tudomtam végülis hogy az egymás melletti csomópontokat hogy vizsgáljam.
Hogy kellet volna ezt rendesen megcsinálni?
válasza:Okj vizsga előtt álló kódmajom alatti lény vagyok, programozáshoz kb 1 éve van közöm.
Nem igazán foglalkoztam eddig bináris fákkal nagyon, de elsőre nekem az jutott eszembe, hogy valahogy egy fűrészfogas/kétdimenziós tömbhöz hasonlító adatszerkezetbe kéne beleerőszakolni, úgy már könnyebb lenne összeadogatni a közepét. Nem biztos, hogy optimális a megoldásom, és még az sem biztos, hogy egyáltalán logikailag helyes, de két tesztesetre jó eredményt adott:
Kapcsolódó kérdések:
Minden jog fenntartva © 2025, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!