Constraints

• 1 <= n <= 100000
• 0 <= len(prerequisites) <= 200000
• 0 <= course, prerequisite < n for every prerequisite pair
• The graph may be disconnected
• The graph may contain cycles

Examples

Solution

def solution(n, prerequisites):
    import heapq

    graph = [[] for _ in range(n)]
    indegree = [0] * n

    for course, prereq in prerequisites:
        graph[prereq].append(course)
        indegree[course] += 1

    available = [course for course in range(n) if indegree[course] == 0]
    heapq.heapify(available)

    order = []

    while available:
        course = heapq.heappop(available)
        order.append(course)

        for next_course in graph[course]:
            indegree[next_course] -= 1
            if indegree[next_course] == 0:
                heapq.heappush(available, next_course)

    if len(order) != n:
        return []

    return order

Time complexity: O((n + m) log n), where m is len(prerequisites), because each course may be pushed/popped from the heap and each edge is processed once.. Space complexity: O(n + m) for the adjacency list, indegree array, heap, and result..

Hints

1. Track how many prerequisites each course still has using an indegree array.
2. Courses with indegree 0 can be taken immediately; if you cannot process all courses, a cycle exists.

Constraints

• 0 <= len(tree) <= 100000
• -1 is reserved as the missing-child sentinel
• All actual node values are non-negative integers
• The input list is a valid standard level-order encoding of a binary tree

Examples

Solution

def solution(tree):
    from collections import deque

    if not tree or tree[0] == -1:
        return []

    class Node:
        __slots__ = ('val', 'left', 'right')

        def __init__(self, val):
            self.val = val
            self.left = None
            self.right = None

    root = Node(tree[0])
    queue = deque([root])
    index = 1

    while queue and index < len(tree):
        node = queue.popleft()

        if index < len(tree):
            if tree[index] != -1:
                node.left = Node(tree[index])
                queue.append(node.left)
            index += 1

        if index < len(tree):
            if tree[index] != -1:
                node.right = Node(tree[index])
                queue.append(node.right)
            index += 1

    def is_leaf(node):
        return node.left is None and node.right is None

    result = [root.val]

    current = root.left
    while current is not None:
        if not is_leaf(current):
            result.append(current.val)
        if current.left is not None:
            current = current.left
        else:
            current = current.right

    if not is_leaf(root):
        stack = [root]
        while stack:
            node = stack.pop()
            if is_leaf(node):
                result.append(node.val)
            else:
                if node.right is not None:
                    stack.append(node.right)
                if node.left is not None:
                    stack.append(node.left)

    right_boundary = []
    current = root.right
    while current is not None:
        if not is_leaf(current):
            right_boundary.append(current.val)
        if current.right is not None:
            current = current.right
        else:
            current = current.left

    result.extend(reversed(right_boundary))
    return result

Time complexity: O(N), where N is the number of entries/nodes represented by the input tree. Each node is built and visited a constant number of times.. Space complexity: O(N) for the constructed tree and auxiliary queues/stacks..

Hints

1. Do not add leaves while collecting the left or right boundary; collect all leaves in a separate pass to avoid duplicates.
2. Collect the right boundary top-down into a temporary list, then reverse it before appending to the answer.