"Kérdés":
Adott egy bináris keresési fa (BST) root és egy val egész szám.
Keresse meg a BST-ben azt a csomópontot, amelynél a csomópont értéke val, és adja vissza az adott csomóponttal gyökerező részfát. Ha ilyen csomópont nem létezik, adja vissza a null értéket.
1. példa:
Input: root = [4,2,7,1,3], val = 2 Output: [2,1,3]
Megoldás:
Az adott feladatban van egy értékünk, amit az adott bináris keresőfában kell keresnünk.
A bináris keresési fák esetében tudjuk, hogy a bal oldali részfa kisebb, mint a gyökérérték, a jobb oldali részfa pedig nagyobb, mint a gyökérérték.
Így könnyen megkereshetjük az értéket egy bináris keresési fában a hagyományos bináris fákhoz képest.
Első lépésünk annak ellenőrzése, hogy a root értéke null.
if(root == NULL)
return root;
Létrehozunk egy új csomópontot, amelyet végeredményként adunk vissza.
TreeNode* node = new TreeNode();
Mivel tudjuk, hogy a bal oldali részfa kisebb, mint a root, ezért ellenőrizni fogjuk, hogy az érték kisebb-e, mint a gyökér. Ha igen, akkor ezt az értéket fogjuk keresni a bal oldali részfában.
if(val < root -> val)
node = searchBST(root -> left, val);
Hasonlóképpen ellenőrizzük, hogy az érték nagyobb-e, mint a gyökér, ezért a megfelelő részfában fogunk keresni.
else if(val > root -> val)
node = searchBST(root -> right, val);
Ha ezek közül egyik sem működik, akkor a csomópontot egyenlővé tesszük a gyökérrel.
else
node = root;
Most az utolsó lépés a korábban létrehozott csomópont visszaadása.
return node;
Az alábbiakban látható az adott probléma teljes megvalósítása:
Köszönöm, hogy elolvasta!
S.
