Leetcode 199 Binary Tree Right Side View

Soru

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Örnek 1

Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]

Örnek 2

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

Çözüm

• Bir binary tree (ikili ağaç) verildiğinde, sağdan bakıldığında görülen düğümlerin listesini döndürmemiz isteniyor.
• Bu soruyu BFS (Genişlik Öncelikli Arama) veya DFS (Derinlik Öncelikli Arama) ile çözebiliriz.
• BFS (Level Order - Kuyuğa Dayalı Çözüm)
• Ağaç seviyelerini level order (katman bazlı) BFS ile gezeriz.
• Her seviyede en sağdaki düğümü alırız.
• DFS (Sağdan Öncelikli Derinlemesine Arama)
• Önce sağ çocuğa giderek DFS yaparsak, her seviyede ilk ziyaret edilen düğüm sağ taraftan görülen düğüm olur.
• Her seviyede sadece ilk düğümü ekleriz.
• Eğer ağacın çok derin olduğunu biliyorsan, BFS kullan çünkü DFS stack overflow hatasına sebep olabilir. Ama genellikle DFS daha az bellek tüketir.

Code

from collections import deque

class Solution:
    def rightSideView(self, root):
        if not root:
            return []
        
        result = []
        queue = deque([root])
        
        while queue:
            level_size = len(queue)
            
            for i in range(level_size):
                node = queue.popleft()
                
                # Eğer bu seviyenin en sağındaki düğümse
                if i == level_size - 1:
                    result.append(node.val)
                
                # Önce sol, sonra sağ çocukları ekle
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        
        return result

Complexity

• Time complexity (Zaman Karmaşıklığı): O(N) çünkü her düğüm bir kez ziyaret edilir.

• Space complexity (Alan Karmaşıklığı): O(N) en kötü durumda kuyrukta tüm seviyedeki düğümler tutulur.

Code

class Solution:
    def rightSideView(self, root):
        result = []
        
        def dfs(node, depth):
            if not node:
                return
            
            # Eğer bu seviyede ilk kez bir düğüm ziyaret ediliyorsa, ekle
            if depth == len(result):
                result.append(node.val)
            
            # Önce sağ çocuğa git, sonra sol çocuğa
            dfs(node.right, depth + 1)
            dfs(node.left, depth + 1)
        
        dfs(root, 0)
        return result

Complexity

• Time complexity (Zaman Karmaşıklığı): O(N) çünkü her düğüm bir kez ziyaret edilir.

• Space complexity (Alan Karmaşıklığı): O(H) (H = ağacın yüksekliği, dengeli ağaçta O(logN), düz ağaçta O(N)).