Esimese sügavuse otsingu algoritm, et kontrollida, kas kaks väljendipuud on samaväärsed

Binaaravaldiste puu on teatud tüüpi binaarpuu, mida kasutatakse aritmeetiliste avaldiste esitamiseks. Igal binaarse avaldisepuu sõlmel on kas null või kaks alampunkti. Lehesõlmed (0 lapsega sõlmed) vastavad operandidele (muutujatele) ja sisemised sõlmed (kahe lapsega sõlmed) vastavad operaatoritele. Selles ülesandes käsitleme ainult operaatorit ‘+’ (st liitmist).

väljend-kaks-puu

Teile antakse kahe binaarse avaldisepuu juured, root1 ja root2. Tagastab tõene, kui kaks binaarset avaldisepuud on samaväärsed. Vastasel juhul tagastage vale.

Kaks binaarset avaldisepuud on samaväärsed, kui nende väärtus on sama, olenemata muutujate seadistamisest.

Järeltegevus: Mida muudate oma lahenduses, kui puu toetab ka operaatorit ‘-‘ (st lahutamist)?

Näide 1:
Sisend: root1 = [x], root2 = [x]
Väljund: tõene

Näide 2:
sisend: root1 = [+,a,+,null,null,b,c], root2 = [+,+,b,c,a]
Väljund: tõene
Selgitus: a + (b + c) == (b + c) + a

Näide 3:
Sisend: root1 = [+,a,+,null,null,b,c], root2 = [+,+,b,d,a]
Väljund: vale
Selgitus: a + (b + c) != (b + d) + a

Piirangud:
mõlema puu sõlmede arv on võrdne, paaritu ja vahemikus [1, 4999].
Node.val on ‘+’ või ingliskeelne väiketäht.
On garanteeritud, et antud puu on kehtiv binaaravaldise puu.

Vihjed:
loendage iga muutuja puhul, mitu korda see esimeses puus esines.
Tehke sama teise puuga ja kontrollige, kas mõlema puu arv on sama.

Esimese sügavuse otsingu algoritm räsitabeliga

Kuna avaldisepuu on binaarne ja võib sisaldada ainult ühte plussmärki. Seetõttu saame mõlemal kahendväljenduse puul läbi viia esimese sügavuse otsingu algoritmi (DFS) ja iga muutuja üles lugeda. Kaks avaldisepuud on võrdsed, kui mõlemad puud sisaldavad sama arvu muutujaid.

DFS töötab O (N) ajas, kus N on mõlema binaaravaldise puu sõlmede arv. Ruumi keerukus on O(N), kuna me kasutame virna rekursiooni kaudu ja samuti peame registreerima iga muutuja loendurid.

Võrdlemaks, kas kaks räsikaarti on võrdsed (unordered_map ), saame neid lihtsalt võrrelda C++ keeles, kasutades topeltvõrdusmärki.