04.03. List of Depth

Description

Given a binary tree, design an algorithm which creates a linked list of all the nodes at each depth (e.g., if you have a tree with depth D, you'll have D linked lists). Return a array containing all the linked lists.

Example:


Input: [1,2,3,4,5,null,7,8]



        1

       /  \

      2    3

     / \    \

    4   5    7

   /

  8



Output: [[1],[2,3],[4,5,7],[8]]

Solutions

Solution 1: BFS Level Order Traversal

We can use the BFS level order traversal method. For each level, we store the values of the current level's nodes into a list, and then add the list to the result array.

The time complexity is $O(n)$, and the space complexity is $O(n)$, where $n$ is the number of nodes in the binary tree.

Python3JavaC++GoTypeScriptRustSwift

# 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]:
        ans = []
        q = deque([tree])
        while q:
            dummy = cur = ListNode(0)
            for _ in range(len(q)):
                node = q.popleft()
                cur.next = ListNode(node.val)
                cur = cur.next
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            ans.append(dummy.next)
        return ans