Aug 6, 2021

Leetcode 102 Binary Tree Level Order Traversal

Soru

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

Örnek 1

image




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

Örnek 2

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

Çözüm

  • Bir binary tree (ikili ağaç) verildiğinde, level order traversal (seviye seviye gezme) işlemini gerçekleştirip sonucu döndürmemiz isteniyor.
  • Bu soruyu BFS (Breadth-First Search) ile çözebiliriz. BFS, seviyeleri sırayla dolaşmamıza yardımcı olur. BFS için queue (kuyruk) veri yapısını kullanacağız.
  • Root düğümünü kuyruğa ekle.
  • Kuyruktan bir düğüm çıkar ve onun çocuklarını kuyruğa ekle.
  • Aynı seviyedeki tüm düğümleri işlerken aynı listeye ekle.
  • Tüm seviyeleri işleyerek sonucu döndür.

Code

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        res = [] #sonuç listesini oluştururuz.
        
        q = collections.deque() #python que yapsını oluştururuz.
        q.append(root) #que ilk node olan kökü ekleriz.
        
        while q: #que içinde değer olduğu sürece
            qLen = len(q) #que boyutunu alırız.
            level = []    #ağaçdaki basamakların değerlerini burada tutacağız.[3],[9,20]...
            for i in range(qLen):
                node = q.popleft()#quedaki ilk giren değeri al(ilk giren ilk çıkar)
                if node:#node değeri var ise
                    level.append(node.val)#bunu basamağın değer listesine ekle
                    q.append(node.left) #sol dalında node var ise queya ekle
                    q.append(node.right)#sağ dalında node var ise queya ekle
            if level:#eğer basamakta değer var ise sonuç listesine ekle
                res.append(level)
        return res

Complexity

  • Time complexity :O(n) Çünkü her düğümü yalnızca bir kez ziyaret ediyoruz.
  • Space complexity :O(n) En kötü durumda, kuyrukta bir seviyedeki tüm düğümler tutulacağı için O(N) olabilir.