g u t x .com.tr İpek yolu - Çin'i anlamaya götürürüm

Temel LeetCode algoritma problemi 47. gün: N-ary ağaç geçişi

Algoritmalar hakkında çok karışık olan makaleler nasıl yazılır. Son olarak, yazmaya en basit seviyeden başlamanın daha iyi olacağını düşünüyorum. Başlangıçtan itibaren, yapay zeka, makine öğrenimi algoritmaları ve çok sayıda matematik ve optimizasyon bilgisi gibi bazı ağır ağırlıklara sahip olacağım. Sanırım çok bunalıma girecek. Elbette Bunu yapamayabilirim, doğru.

Her soru için iki dilde, statik dil ve dinamik dilde çözüm vermeyi planlıyorum.

Uygulama dilleri olarak C dili, Python ve Java'yı seçiyorum.Kısıtlı alan nedeniyle, diğer dillerin uygulanmasıyla ilgilenen arkadaşlar, lütfen kendiniz deneyin.

LeetCode 429. N-ary Ağaç Seviyesi Sıra Geçişi

Sorun Açıklaması:

N-ary ağaç verildiğinde, düğüm değerinin geçişini döndür. (Yani, soldan sağa doğru katman katman çapraz).

Not:

Ağacın derinliği 1.000'i geçmeyecektir.

Ağaçtaki toplam düğüm sayısı 5000'i geçmeyecektir.

Misal:

C ++ dil uygulaması:

Ağaç hiyerarşisini geçmek için en geniş ilk algoritmayı kullanabiliriz.

Ağacı geçmek için en geniş algoritma ile ilgili olarak, önceki soru "44. gün" deki java ve python uygulamasında ikili ağacın üzerinden geçmek için enine ilk algoritmayı kullandık.

N-ary ağacı geçmek ile ikili ağaçtan geçmek arasında temel bir fark yoktur.

Katman dizisi geçişi, "44. Gün" deki C ++ uygulamasına benzer şekilde özyinelemeli yöntemlerle de uygulanabilir.

Bugün, bu sorunu çözdüğümüz tüm uygulamalar özyineleme ile uygulanmaktadır, çünkü bu uygulama kodu görece akıcı hale getirilmiştir. Enine ilk algoritmanın uygulanmasıyla ilgili olarak, bunu kendiniz yazmayı deneyebilirsiniz, herhangi bir sorunuz varsa, yorumlarda sorabilirsiniz.

Kodun 1'den 6'ya kadar olan satırları optimize edilmiş kodlardır ve "19. Gün" de ayrıntılı olarak açıklanmıştır, bu yüzden onları buraya yazmayacağım.

LevelOrder ana işlevinde, önce iki boyutlu bir res vektörü tanımlayın, ardından res'i doldurmak için doLevelOrder özel işlevini çağırın ve son olarak res döndür.

DoLevelOrder işlevi 3 nesli kabul eder, ilki alt ağacın düğümü, ikincisi doldurulacak iki boyutlu vektör ve üçüncü parametre ise tüm ağaçtaki geçerli düğümün düzey sayısıdır.Seviye sayısının 0'dan başladığını kabul ediyoruz. .

DoLevelOrder mantığı:

Şu anda boş bir düğümse, doğrudan dönün. Mevcut düğüm boş bir düğüm değilse, val değerini listeye doldurmalıyız. Ancak bazen, doldurmak istediğiniz alt vektör listede henüz bulunmadığından, 12. satırda bir yargıya varırız. Şu anda, listeye boş bir vektör eklemeli ve sonra onu val ile doldurmalıyız.

Son olarak, özyineleme tüm alt düğümlerinde gerçekleştirilir.Bunlar alt düğümler oldukları için, üçüncü parametre olan katman sayısı 1 artırılmalıdır.