이진 트리 수준 순서 탐색 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: []

이진 트리 수준 순서 탐색 Python 솔루션

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. 큐(또는 재귀 스택)가 모든 수준에서 최대 노드 수를 유지하므로 공간 복잡도는 O(M)입니다.

참고:

1. LeetCode 문제
2. 리트코드솔루톤
3. 폭 우선 검색

위 내용은 이진 트리 수준 순서 탐색 Leetcode의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!