Aug 6, 2021

Leetcode 102 Binary Tree Level Order Traversal





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

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

Soruda bize bir binary tree veriliyor ve bu binary tree deki her basamağı kökten başlayarak yazmamız isteniyor.
Burada BFS ve que yapısı kullanarak soruyu çözebiliriz.
İlk olarak kökü que ekleriz [1]
Daha sonra programdaki adımları izleyerek 1’i quedan çıkarır onun sağ ve sol dallarındaki nodeları ekleriz[2,3] 1’i basamak listesine(level) ekler sonra da bu listeyi sonuç listesine ekleriz. -Ve bu şekilde que içerisindeki değerler bitene kadar devam ederiz.

# 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