102. 이진 트리 수준 순회 🚀

솔루션 개발:

질문

이 기사에서는 Leetcode의 '102. Binary Tree Level Order Traversal' 질문을 다룰 것입니다. 이 질문은 보통 질문으로 평가됩니다.

의문:

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

예시:

    3
   / \
  9  20
    /  \
   15   7

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

질문 설명

이 질문의 등급은 보통입니다. 이 이진 트리 질문에 대해 정확하다고 생각합니다.

따라서 순회해야 하는 이진 트리가 제공됩니다. 노드 값의 레벨 순회를 반환해야 합니다. 이것이 의미하는 바는 이진 트리의 각 계층이 해당 배열에 무엇이 있는지 나타내는 자체 배열을 가져야 한다는 것입니다.

즉, 이진 트리에 10개의 레이어가 있는 경우 10개의 배열이 있어야 합니다. 이진 트리의 10개 레이어를 나타냅니다.

이제 Level Order Traversal 에 익숙할 것입니다. 이에 익숙하지 않은 경우 이에 대해 읽을 수 있습니다here . 마스터가 될 때까지 이 순회 기술을 연습하는 것이 좋습니다. 그 지식 없이는 이 질문을 풀 수 없기 때문입니다.

권장 지식

Binary Tree

Depth First Search

In-order traversal

Level Order Traversal

Queue

우리는 무엇을 알고 있습니까?

이진 트리가 주어졌습니다.

우리 나무에는 여러 레이어가 있습니다.

이러한 계층은 트래버스하고 저장해야 합니다.

각 레이어에는 자체 행이 있어야 합니다.

이러한 배열의 컬렉션을 반환합니다. 행의 배열이 될 것입니다.

어떻게 할 것인가:

우리는 반복적인 계층 순회(In-order) 알고리즘의 변형을 수행할 것입니다. 이는 레이어 형식으로 각 노드를 방문한다는 의미입니다. 이를 위해question 이 작업을 수행하는 방법을 이미 알고 있어야 합니다.

일반 레벨 순회와 다른 점은 for 루프를 사용하여 각 레이어를 반복한다는 것입니다. 각 레이어는 대기열에 있는 항목으로 표시됩니다. 여기서 주요 차이점은 해당 레이어에 있는 노드만 방문한다는 것이지만, 그럼에도 불구하고 다음에 어떤 노드가 오는지 알 것입니다. 조금 혼란 스럽습니다.

따라서 각 레이어에 대해 주어진 노드 값을 row array에 추가한 다음 노드의 자식을 대기열에 추가할 것입니다. '하지만 분명히 우리는 그런 식으로 전체 트리를 통과하게 될 것이고 레이어별로 가지 않을 것입니다!!'. 예, 대기열 길이를 추가하기 전에 대기열 길이를 추적하지 않은 경우에 해당할 수 있지만 계속 추적합니다. 그래서 우리는 항상 레이어의 길이를 알고 있습니다.

먼저 트리의 레벨 순서 순회를 위해 queue를 선언할 것입니다. 또한 반환 값이 될 level_order_array를 선언할 것입니다. 여기에서 각각row을 푸시합니다.

row 배열을 선언할 것입니다. 물론 각 이진 트리 레이어를 대표합니다.

따라서 대기열의 길이를 저장하겠습니다. 현재 레이어 길이의 길이가 됩니다. 해당 계층의 각 노드에 대해 row 배열에 추가할 것입니다. 자녀를 대기열에 추가하는 동안. 그러나 우리는 해당 레이어의 노드만 원하기 때문에 주어진 queue 의 초기 길이에 대해서만 for 루프를 수행할 것입니다.

빅오 표기법:

시간 복잡도: O(n) | 여기서 n은 이진 트리의 노드 수 | 트리 내의 모든 노드를 순회할 것입니다.

공간 복잡도: O(q) | 여기서 q는 이진 트리 대기열의 길이입니다

.

리트코드 결과:

제출 링크 참조:

런타임: 77ms, 이진 트리 수준 순서 순회

에 대한 JavaScript 온라인 제출의 64.38%보다 빠름

메모리 사용량: 44.5MB, 이진 트리 수준 순서 탐색

에 대한 JavaScript 온라인 제출의 35.08% 미만

해결책

var levelOrder = function (root) {

    // Empty tree
    // Return a empty array
    if (!root) {
        return [];
    }

    // Level Order Array, will store each row of the tree
    let level_order_array = [];
    let queue = [root];

    // We're going to be using a iterative approach to this.
    // With use of a queue we're able to achieve level order traversal.
    while (queue.length) {

        // We're going to create a new row each time
        // we encounter a new level.
        let row = [];

        // This is the important part.
        // We keep track of the initial length of the queue
        // We do this because, as we iterate through the queue we don't
        // want to accidentally pick up items from another.
        let queue_len = queue.length;

        // So for every item currently in the queue
        // we're going to add it to the row
        // All the while adding new items to the queue,
        // but because we kept memory of the input length
        // we will only ever pick up the items for that row.
        for (let i = 0; i < queue_len; i++) {

            // Get the node, by popping it off the queue
            let node = queue.pop();

            // Add the node to the row (This row is the given layer)
            row.push(node.val);

            // Just like in a normal level order traversal,
            // when we see a child node, we add it to the queue,
            // but because we kept memory of the input length
            // we won't technically run these children items
            // until we reach their row.
            node.left ? queue.unshift(node.left) : null;
            node.right ? queue.unshift(node.right) : null;
        }

        // So we have gone through the entire queue.
        // Push that row to the level order array.
        level_order_array.push(row);
    }

    return level_order_array;
};