LeetCode Temel Algoritma Problemi Bölüm 102: Bir ikili ağacın tüm sol yaprak düğümlerinin toplamını bulun
Teknik iyileştirme aşamalı bir süreçtir, bu yüzden bahsettiğim leetcode algoritması soruları en basit seviyeden başlar, sonra orta zorluk derecesine ve nihayet zor zorluğa.
Şu anda, uygulama dili olarak C dili, Python ve Java'yı seçiyorum çünkü bu üç dil oldukça tipik. Sınırlı alan ve enerji nedeniyle, diğer dilleri uygulamakla ilgilenen arkadaşlar, lütfen kendiniz deneyin.
Temel zorluk hemen hemen aynı olduğunda daha fazla içerik eklemeyi planlıyorum.İşletim sisteminden protokol yığınına, dağıtılmış sohbetten büyük veri çerçevesine, büyük veriden yapay zekaya kadar konuşabilirim ...
Herhangi bir sorunuz varsa makaleden sonra yorum yapabilir veya bana özel mesaj gönderebilirsiniz. .
Paylaşmaya devam edeceğim, bu yüzden lütfen dikkat edin.
LeetCode 404. Sol Yaprakların Toplamı
Sorun Açıklaması:
Belirli bir ikili ağacın tüm sol yapraklarının toplamını hesaplayın.
Misal:
C dili uygulaması:
Tüm yaprak düğümleri bulma yönteminin, sol ve sağ alt ağaçların yaprak düğüm değerlerini yinelemeli olarak eklemek olduğunu biliyoruz.
Bu soru sadece bu temelde bir koşul ekler, yani bir yaprak düğümün bir sol yaprak düğüm olup olmadığını belirlemek için bir yargı eklenmesi gerekir.
Burada iki yöntemimiz var.
ilk yöntem:
Doğrudan bir sol yaprak düğüm olup olmadığına karar verin, öyleyse, değerinin toplamını ve sağ kardeş düğümün özyinelemeli sonucunu döndürün, çünkü kardeş düğüm mutlaka bir yaprak düğüm değildir, bu nedenle özyineleme gereklidir.
Bir düğümün sol ve sağ düğümleri yaprak düğümler değilse, sol ve sağ düğümlerin özyinelemeli toplamı döndürülür ve anlaşılması kolaydır.
kod aşağıdaki gibi gösterilir:
İkinci yöntem:
Bu, geçiş sırasında sonraki düğümün sol düğüm olup olmadığını işaretlemek için yeni bir özyinelemeli işlev tanımlamayı gerektirir.
Aşağıda geçilecek düğüm mevcut düğümün sol düğümüyse, sol düğümü yeni işleve geçirmenin yanı sıra, bunu bir sol düğüm olarak işaretlemek için yeni işleve iletilen gerçek bir değer de vardır.Aynı şekilde sağ düğüm ise Yeni işleve doğru düğümü ve bir yanlışı iletin. Daha sonra yeni işlev işlenirken, önce geçirilen parametreye bakın ve eğer sol düğüm olarak işaretlenmişse değeri döndürülür. Aksi takdirde, düğümün alt düğümlerini yinelemeye ve toplamlarını döndürmeye devam edin.
kod aşağıdaki gibi gösterilir:
Kod açısından bakıldığında, bu iki uygulama çok benzer, ancak ilkeler biraz farklı.
Algoritma karmaşıklıkları aynıdır ve performansları temelde aynıdır.
Python dilinin uygulanması:
Python birinci yolla uygulanır ve ikinci şekilde okuyucular bunu kendileri denemelidir.
kod aşağıdaki gibi gösterilir:
Java dilinin uygulanması:
Java'nın uygulanması ilk yoldur ve ikinci yol okuyucuların denemesidir.
kod aşağıdaki gibi gösterilir:
