Leetcode پیمایش ترتیب سطح درخت باینری

با توجه به ریشه یک درخت باینری، پیمایش ترتیب سطح مقادیر گره های آن را برگردانید. (یعنی از چپ به راست، سطح به سطح).

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

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

Example 3:
Input: root = []
Output: []

راه حل پایتون پیمایش ترتیب سطح درخت دودویی

class Solution(object):
    def levelOrder(self, root):
        if not root:
            return []
        Q = deque([root])
        levels = [[root.val]]
        temp = deque()
        while Q:
            node = Q.popleft()
            if node.left: temp.append(node.left)
            if node.right: temp.append(node.right)
            if not Q:
                if temp:
                    levels.append([n.val for n in temp])
                Q = temp
                temp = deque()
        return levels

الگوی کدگذاری مورد استفاده در این راه حل

الگوی کدگذاری مورد استفاده در تمامی پیاده سازی های ارائه شده است جستجوی اول پهنای درخت (BFS).
این الگو معمولاً یک درخت را به صورت سطح طی می کند و همه گره ها را در عمق فعلی قبل از حرکت به عمق بعدی پردازش می کند.
BFS با استفاده از یک ساختار داده صف برای پیگیری گره ها در هر سطح پیاده سازی می شود.

پیچیدگی زمان و مکان برای این راه حل

1. پیچیدگی زمانی O(N) است زیرا هر گره یک بار بازدید می شود.
2. پیچیدگی Space O(M) است زیرا صف (یا پشته بازگشتی) حداکثر تعداد گره ها را در هر سطح نگه می دارد.

مرجع:

1. مشکل LeetCode
2. LeetCode Soluton
3. جستجوی عرض-اول