問題

力扣

給定一棵二叉樹，設(shè)計一個算法，創(chuàng)建含有某一深度上所有節(jié)點的鏈表（比如，若一棵樹的深度為 D，則會創(chuàng)建出 D 個鏈表）。返回一個包含所有深度的鏈表的數(shù)組。

示例：

輸入：[1,2,3,4,5,null,7,8]
        1
       /  \ 
      2    3
     / \    \ 
    4   5    7
   /
  8

輸出：[[1],[2,3],[4,5,7],[8]]

思路

BFS

層次遍歷，每層節(jié)點單獨構(gòu)成一個單鏈表。

代碼

Python3

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def listOfDepth(self, tree: TreeNode) -> List[ListNode]:
        import collections

        if not tree:
            return []
        
        queue = collections.deque()
        queue.append(tree)
        res = []
        # BFS
        while queue:
            n = len(queue)
            for i in range(n):
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
                # 當前層的第一個節(jié)點
                if i == 0:
                    # 頭節(jié)點
                    head = ListNode(node.val)
                    tmp = head
                else:
                    tmp.next = ListNode(node.val)
                    tmp = tmp.next
            # 這里加入res的是head
            res.append(head)
        return res

鏈接

GitHub