Leetcode 104 Maximum Depth of Binary Tree

Soru

Given the root of a binary tree, return its maximum depth.

A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Örnek 1

Input: root = [3,9,20,null,null,15,7]
Output: 3

Örnek 2

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

Örnek 3

Input: root = []
Output: 0

Örnek 4

Input: root = [0]
Output: 1

Çözüm DFS

• “104. Maximum Depth of Binary Tree” sorusu, verilen bir ikili ağacın maksimum derinliğini (en uzun yol) bulmanızı ister. Bu problemde, ağacın kökünden en uzak yaprak düğümüne olan yol boyunca geçilen kenar sayısının maksimumu hesaplanır.
• Girdi: İkili bir ağacın kök düğümü (root).
• Çıktı: Ağacın maksimum derinliği.
• Bu problem genellikle özyinelemeli (recursive) veya yinelemeli (iterative) yöntemler kullanılarak çözülür. Her iki yöntem de ağacın her düğümünü ziyaret ederek en derin yaprak düğümüne ulaşmayı amaçlar.
• Özyinelemeli Çözüm (DFS): Özyinelemeli çözüm, bir derinlik öncelikli arama (Depth-First Search, DFS) kullanarak her düğüm için sol ve sağ alt ağaçların derinliklerini karşılaştırır ve her düzeyde maksimum olanı alır.
• Yinelemeli Çözüm (BFS): Yinelemeli çözümde, genellikle bir genişlik öncelikli arama (Breadth-First Search, BFS) kullanılır. Her seviye tamamlandığında, derinlik bir arttırılır.
• Çalışma Mekanizması:
• Özyinelemeli Yöntem: Her düğüm için sol ve sağ alt ağaçların maksimum derinlikleri hesaplanır ve en büyük olanına bir eklenir (mevcut düğümün derinliği).
• Yinelemeli Yöntem: Her seviyede, o seviyedeki tüm düğümler işlenir ve seviye sayısı bir arttırılır.

Code Özyinelemeli Çözüm (DFS):

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

class Solution:
    def maxDepth(self, root):
        if not root:
            return 0
        left_depth = self.maxDepth(root.left)
        right_depth = self.maxDepth(root.right)
        return max(left_depth, right_depth) + 1

Code Yinelemeli Çözüm (BFS):

from collections import deque

class Solution:
    def maxDepth(self, root):
        if not root:
            return 0
        queue = deque([root])
        depth = 0
        while queue:
            level_length = len(queue)
            for i in range(level_length):
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            depth += 1
        return depth

Complexity

• Time complexity (Zaman Karmaşıklığı): Her iki yöntem için de O(n), burada n ağaçtaki toplam düğüm sayısıdır. Her düğüm bir kez işlenir.
• Space complexity (Alan Karmaşıklığı):
• Özyinelemeli için O(h), burada h ağacın yüksekliği. Bu, çağrı yığınında yer kaplar ve ağaç dengesizse kötüleşebilir.
• Yinelemeli (BFS) için O(w), burada w ağacın en geniş seviyesindeki maksimum düğüm sayısıdır.