Leetcode 문제를 해결하고 꿈의 회사에서 제안 받기

문제 102. 이진 트리 수준 순회



이 시리즈에서는 YouTube 채널에서 볼 수 있는 Leetcode 매체 문제를 친구들과 라이브로 해결할 것입니다. 오늘 우리는 문제 Leetcode: 102. 이진 트리 수준 순서 순회를 할 것입니다.

나에 대해 조금, 과거에 Uber India와 Amazon India에서 제안을 받았고 현재 암스테르담의 Booking.com에서 일하고 있습니다.

알고리즘을 배우게 된 동기

Solve Leetcode Problems and Get Offers From Your Dream Companies

문제 설명

a binary tree 의 루트가 주어지면 해당 노드 값의 레벨 순회를 반환합니다. (즉, 왼쪽에서 오른쪽으로, 레벨별로).

예 1:

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

Output: [[3],[9,20],[15,7]]

예 2:

Input: root = [1] 

Output: [[1]] 

예 3:

Input: root = [] 

Output: []

제약:

트리의 노드 수가 [0, 2000] 범위에 있습니다.

-1000 <= Node.val <= 1000

유튜브 토론

해결책

이것은 표준coding problems on Binary Tree 중 하나입니다. 이 문제에서 노드 값의 레벨 순서 순회를 반환해야 합니다. (즉, 왼쪽에서 오른쪽으로, 레벨별로). 이는 대기열의 도움으로 트리에서 BFS를 사용하여 수행할 수 있습니다. 각 노드에 대해 먼저 노드를 방문한 다음 하위 노드를 FIFO 대기열에 넣습니다.

빈 대기열 만들기 q

temp_node = 루트

temp_node가 NULL이 아닌 동안 루프

ㅏ. temp_node->data를 인쇄합니다.

비. temp_node의 자식 대기열에 넣기(왼쪽에서 오른쪽으로)

씨. q에서 노드를 대기열에서 뺍니다.

The following code implements this algorithm

이 자습서에서 BFS에 대해 자세히 알아볼 수 있습니다.
How to use Breath Fast Search Pattern for craking coding Interviews

C++ 솔루션

자바 솔루션

복잡성 분석

시간복잡도는 O(n)

공간 복잡도는 O(n)

읽어주셔서 감사합니다. 더 많은 LeetCode 문제를 보려면 이 출판물을 팔로우하세요!😃

LeetCode Simplified

50+ Data Structure and Algorithms Interview Questions for Programmers