Leetcode 543 Diameter of Binary Tree

Soru

Given the root of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

The length of a path between two nodes is represented by the number of edges between them.

Örnek 1

Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].

Örnek 2

Input: root = [1,2]
Output: 1

Çözüm DFS

• Bu problem, ikili bir ağacın çapını (diameter) bulmanızı ister. Çap, herhangi iki düğüm arasındaki en uzun yol boyunca geçen kenar sayısıdır. Bu yol kökten geçmek zorunda değildir; herhangi bir düğümden başlayabilir ve herhangi bir düğümde bitebilir.
• Girdi: İkili bir ağacın kök düğümü (root).
• Çıktı: Ağacın çapını (en uzun yol boyunca geçen kenar sayısı) döndür.
• Bu soruyu çözmek için DFS (derinlik öncelikli arama) kullanarak her düğümde sol ve sağ alt ağaçların derinliğini hesaplar ve bu derinliklerin toplamını çap olarak değerlendiririz. Her düğüm için bu değeri kontrol eder ve maksimum olanı kaydederiz.
• Çözüm Açıklaması:
• DFS ile her düğüm için derinlik hesaplanır.
• Sol ve sağ alt ağaçların derinlik toplamı, o düğümdeki çapı verir.
• Global self.diameter değişkeni ile her düğümdeki çap kontrol edilir ve maksimum değeri kaydederiz.
• DFS fonksiyonu, her düğümün maksimum derinliğini döndürür (max(left, right) + 1).

Code

    class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        self.diameter = 0
        
        def dfs(node):
            if not node:
                return 0
            # Sol ve sağ alt ağaçların derinliğini hesapla
            left_depth = dfs(node.left)
            right_depth = dfs(node.right)
            
            # Çapı güncelle: sol + sağ uzunluklarını kontrol et
            self.diameter = max(self.diameter, left_depth + right_depth)
            
            # Bu düğümün derinliğini döndür
            return max(left_depth, right_depth) + 1
        
        dfs(root)
        return self.diameter

Complexity

• Time complexity (Zaman Karmaşıklığı) : O(n), burada n ağacın toplam düğüm sayısıdır. Her düğüm bir kez ziyaret edilir.

• Space complexity (Alan Karmaşıklığı) :Ortalama durumda O(h), burada h ağacın yüksekliğidir (çağrı yığınında kullanılan alan). Dengesiz bir ağaçta bu O(n) olabilir.