Syvyys ensin -hakualgoritmi tarkistaaksesi, ovatko kaksi lausekepuuta samanarvoisia

Binäärilausekepuu on eräänlainen binääripuu, jota käytetään edustamaan aritmeettisia lausekkeita. Jokaisella binaarilausekepuun solmulla on joko nolla tai kaksi alapistettä. Lehtisolmut (solmut, joissa on 0 lasta) vastaavat operandeja (muuttujia) ja sisäiset solmut (solmut, joissa on kaksi lasta) vastaavat operaattoreita. Tässä tehtävässä huomioidaan vain ‘+’-operaattori (eli summaus).

lauseke-binääri-puu

Sinulle annetaan kahden binaarilausekepuun juuret, juuri1 ja juuri2. Palauttaa tosi, jos kaksi binaarilausekepuuta ovat samanarvoisia. Muussa tapauksessa palauta false.

Kaksi binaarilausekepuuta ovat ekvivalentteja, jos ne evaluoivat samaan arvoon riippumatta siitä, mihin muuttujat on asetettu.

Seuranta: Mitä muutat ratkaisussasi, jos puu tukee myös ‘-‘-operaattoria (eli vähennyslaskua)?

Esimerkki 1:
Tulo: root1 = [x], root2 = [x]
Tulos: tosi

Esimerkki 2:
Syöttö: root1 = [+,a,+,nolla,null,b,c], root2 = [+,+,b,c,a]
Tulos: true
Selitys: a + (b + c) == (b + c) + a

Esimerkki 3:
Syöttö: root1 = [+,a,+,nolla,null,b,c], root2 = [+,+,b,d,a]
Tulos: epätosi
Selitys: a + (b + c) != (b + d) + a

Rajoitukset:
Solmujen lukumäärä molemmissa puissa on yhtä suuri, pariton ja alueella [1, 4999].
Node.val on ‘+’ tai pieni englanninkielinen kirjain.
On taattu, että annettu puu on kelvollinen binäärilausekepuu.

Vihjeitä:
Laske kunkin muuttujan kohdalla, kuinka monta kertaa se esiintyi ensimmäisessä puussa.
Tee sama toiselle puulle ja tarkista, onko molemmissa puussa sama luku.

Syvyys ensin -hakualgoritmi hash-taulukolla

Koska lausekepuu on binaarinen ja voi sisältää vain yhden plussymbolin. Siksi voimme suorittaa Depth First Search Algorithmin (DFS) molemmille binäärilausekepuille ja laskea kunkin muuttujan. Nämä kaksi lausekepuuta ovat yhtä suuret, jos molemmat puut sisältävät saman määrän muuttujia.

DFS suoritetaan O(N) -ajassa, missä N on solmujen lukumäärä molemmissa binäärilausekepuissa. Tilan monimutkaisuus on O(N), koska käytämme pinoa rekursion kautta ja meidän on myös tallennettava jokaisen muuttujan laskurit.

Vertaaksemme, ovatko kaksi hash-karttaa yhtä suuret (unordered_map ), voimme yksinkertaisesti verrata niitä C++:ssa käyttämällä kaksoisyhtäysmerkkiä.