Depth First Search Algoritm för att kontrollera om två uttrycksträd är likvärdiga

Ett binärt uttrycksträd är ett slags binärt träd som används för att representera aritmetiska uttryck. Varje nod i ett binärt uttrycksträd har antingen noll eller två barn. Lövnoder (noder med 0 barn) motsvarar operander (variabler), och interna noder (noder med två barn) motsvarar operatorerna. I detta problem tar vi bara hänsyn till ‘+’-operatorn (dvs addition).

uttryck-binärt-träd

Du får rötterna till två binära uttrycksträd, root1 och root2. Returnera sant om de två binära uttrycksträden är ekvivalenta. Annars, returnera falskt.

Två binära uttrycksträd är likvärdiga om de utvärderas till samma värde oavsett vad variablerna är inställda på.

Uppföljning: Vad kommer du att ändra i din lösning om trädet också stöder ‘-‘-operatorn (dvs subtraktion)?

Exempel 1:
Indata: rot1 = [x], rot2 = [x]
Utdata: sant

Exempel 2:
Indata: root1 = [+,a,+,null,null,b,c], root2 = [+,+,b,c,a]
Utdata: sant
Förklaring: a + (b + c) == (b + c) + a

Exempel 3:
Indata: root1 = [+,a,+,null,null,b,c], root2 = [+,+,b,d,a]
Output: false
Förklaring: a + (b + c) != (b + d) + a

Begränsningar:
Antalet noder i båda träden är lika, udda och i intervallet [1, 4999].
Node.val är ‘+’ eller en liten engelsk bokstav.
Det är garanterat att det angivna trädet är ett giltigt binärt uttrycksträd.

Tips:
Räkna för varje variabel hur många gånger den förekom i det första trädet.
Gör samma sak för det andra trädet och kontrollera om antalet är detsamma för båda träden.

Depth First Search Algoritm med Hash-tabell

Eftersom uttrycksträdet är binärt och bara kan innehålla en plussymbol. Därför kan vi utföra Depth First Search Algorithm (DFS) på båda binära uttrycksträden och räkna varje variabel. De två uttrycksträden är lika om båda träden innehåller samma antal variabler.

DFS körs i O(N) -tid där N är antalet noder i båda binära uttrycksträden. Utrymmeskomplexiteten är O(N) eftersom vi använder stack via rekursion och även behöver registrera räknarna för varje variabel.

För att jämföra om två hash-kartor är lika (unordered_map ), kan vi helt enkelt jämföra dem i C++ med det dubbla likhetstecknet.