솔루션 개발:

질문

이 기사에서는 Leetcode의 '199. Binary Tree Right Side View' 질문을 다룰 것입니다.

의문:

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Example:

Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]

질문 설명

이 질문의 등급은 보통입니다. 대부분 정확합니다. 그러나 이것은 Medium 질문을 이미 해결한 경우에만 매체입니다. 이 키Level Order Traversal Pattern를 모르면 이 질문을 이해하기 어려울 것입니다. Level Order Traversal Pattern 을 아는 것이 중요합니다. 이 패턴을 모르시면 Level Order Traversal Question First 해결하세요.

패턴을 이해하지 못하는 경우 읽기를 강력히 권장합니다.

우리가 질문을 받고 있는 것은 우리가 이진 트리의 오른쪽에 서 있다고 상상하는 것입니다. 어떤 노드를 볼 수 있습니까? 즉, 다른 노드 뒤에 숨겨진 노드를 의미하는 오른쪽 가시 노드만 트래버스할 수 있는 경우입니다. 이것은 혼란스럽게 들리지만 실제로는 매우 간단합니다.

권장 지식

Binary Trees

Level Order Traversal

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

이진 트리가 있습니다.

이 이진 트리에 노드가 없을 수 있음

오른쪽 보기 노드를 모두 찾아야 합니다

.

어떻게 할 것인가:

이진 트리의 레벨 순서 순회를 수행할 것입니다. arow의 끝에 도달할 때마다 노드의 값을 배열로 푸시할 것입니다. 이 배열은 가장 오른쪽에 있는 모든 노드가 됩니다. 이렇게 하는 이유는 레벨 순서의 각 행 끝에 순회가 항상 오른쪽 보기에서 표시되기 때문입니다. 행의 모든 ​​마지막 노드가 보이는 노드임을 의미합니다.

변수right_view를 선언하고 빈 배열로 설정하겠습니다. 여기에는 가장 적합한 노드 값이 모두 들어 있습니다.

이진 트리의 레벨 순회를 수행할 것입니다. Level Order Traversal 질문과 똑같은 방식으로. 여기서 각 행의 대기열 길이를 기록하고 대기열 길이만 반복합니다.

행의 마지막 노드에 도달하면 right_view 배열에 추가합니다.

이진 트리의 모든 행을 반복할 때까지 이 작업을 반복합니다.

빅오 표기법:

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

공간 복잡도: O(q) | 여기서 q는 이진 트리에서 가장 긴 행의 번호입니다. 각 행에서 대기열의 길이를 저장해야 하기 때문입니다. 최악의 경우 길이가 n인 대기열이 생깁니다.

리트코드 결과:

제출 링크 참조:

런타임: 72ms, 이진 트리 오른쪽 보기에 대한 JavaScript 온라인 제출의 77.60%보다 빠름

메모리 사용량: 43.8MB, 이진 트리 오른쪽 보기에 대한 JavaScript 온라인 제출물의 64.69% 미만.

해결책

var rightSideView = function (root) {

    // Base case, no nodes given. 
    if (!root) {
        return [];
    }

    // An array to store all the right most nodes
    const right_view = [];

    // A queue for the level order traversal
    const queue = [root];

    // While the queue is not empty, keep going
    while (queue.length) {

        // Make note of the queue length.
        // We do this to perform row by row traversal.
        const q_len = queue.length;

        // Iterate through the queue, end at the row
        for (let i = 0; i < q_len; i++) {

            // Current node
            const node = queue.pop();

            // If the current index is the end of the row,
            // meaning, it's the right most node in the level.
            // Push it to the right_view array.
            if (i === q_len - 1) {
                right_view.push(node.val);
            }

            // Add them. 
            node.left ? queue.unshift(node.left) : null;
            node.right ? queue.unshift(node.right) : null;
        }
    }

    // Return Home!!
    return right_view;
};