솔루션 개발:

질문

이 기사에서는 Leetcode의 '103. Binary Tree Zigzag Level Order Traversal' 질문을 다룰 것입니다.

의문:

Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate > between).

예시:

Input: root = [1,null,0,0,1]
Output: [1,null,0,null,1]
Explanation: 
Only the red nodes satisfy the property "every subtree not containing a 1".
The diagram on the right represents the answer.

질문 설명

이 질문의 등급은 보통입니다. 정확하다고 생각합니다. 여러 면에서 이 질문은 '102. Binary Tree Level Order Traversal'의 후속 질문입니다. 이 질문에 익숙하다면 이 질문을 이해할 수 있을 것입니다.

우리가 요청받은 것은 102. Binary Tree Level Order Traversal 과 동일합니다. 조금 비틀어도 지그재그 방식으로 해야 합니다. 즉, 왼쪽과 오른쪽을 번갈아 가며 사용해야 합니다. 일반적으로 우리는 그냥 갈 것입니다 left -> right . 마치 우리가 책을 읽는 것처럼. 이 질문에서 우리는 가야하지만 left -> right 그런 다음 right -> left . 말 그대로 지그재그.

특이한 순회를 만들어야 하기 때문에 어려워 보일 수 있지만 실제로는 그렇게 어렵지 않습니다. 우리 둘 다 수준 순서 순회가 queue 노드를 저장하기 위해 row가 필요하다는 것을 알고 있습니다. 우리가 해야 할 일은 queue 와 queue 사이에서 stack 를 번갈아 가며 사용하는 것입니다.

그래서 우리가 의 row에 추가할 때마다 우리도 묻습니까? 이 값을 어레이의 시작 또는 끝에 추가합니까? 그게 다야. 😁

권장 지식

Binary Tree

Depth First Search

Level order traversal

102. Binary Tree Level Order Traversal (쉽게 할 수 있음)

Stack

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

이진 트리가 있습니다(대부분 비어 있을 수 있음)

레벨 순서 순회를 나타내는 array 내의 이진 트리 내의 모든 행을 저장해야 합니다.

이진 트리에서 지그재그 방식으로 level order traversal을 수행해야 합니다.

어떻게 할 것인가:

우리는 102. Binary Tree Level Order Traversal 질문과 유사한 솔루션을 구현할 것입니다. queue를 사용하여 row 노드를 저장하는 것입니다. 다음 행으로 이동하는 queue의 모든 노드를 항상 지웠는지 확인합니다.

여기서 주요 차이점은 zigzag와 true 값을 번갈아 사용하기 위해 false라는 플래그 세트가 있다는 것입니다. True는 이동해야 함right -> left을 나타내고 false는 이동해야 함left -> right을 나타냅니다. unshift 및 push 방법을 사용하여 이를 수행합니다.
row에 노드를 추가해야 할 때마다 묻습니다. 이 값을 어레이의 시작 또는 끝에 추가합니까? 따라서 zigzag 플래그가 true인 경우 unshift 작업을 사용하여 배열의 시작 부분에 노드를 추가합니다queue. zigzag 플래그가 false이면 마치 stack 인 것처럼 배열 끝에 노드를 추가합니다.

결국 우리가 달성하는 것은 순회zigzag가 아니라 순회를 모방하는 것입니다. 기술적으로 말해서, 우리는 Binary Tree 방식으로 level order를 순회하고 있습니다. 그러나 노드를 row에 추가하는 방식은 zigzag 방식입니다.

빅오 표기법:

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

공간 복잡도: O(n) | 여기서 n은 이진 트리의 노드 수 | 모든 노드를 level_order 배열에 추가할 것입니다.

리트코드 결과:

제출 링크 참조:

런타임: 69ms, 이진 트리 지그재그 레벨 순서 통과에 대한 JavaScript 온라인 제출의 76.64%보다 빠름.

메모리 사용량: 43.5MB, Binary Tree Zigzag Level Order Traversal에 대한 JavaScript 온라인 제출물의 95.97% 미만.

해결책

var zigzagLevelOrder = function (root) {

    // What we do here is perform the normal
    // level order traversal in rows.
    // But we instead use a stack / queue depending
    // on if we're to zig zag or not.

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

    // So we're going to need a queue for the level order traversal.
    // We're also going to need a level_order array to store all the rows 
    // of the binary tree
    // as well as a flag to invert the order of the rows or not
    // (zig zag). Meaning, if we're going to zig zag, we'll get the first node in the queue
    // if we're not zig zag, we'll get the last node in the queue. (Unshift / pop)
    let queue       = [root];
    let level_order = [];
    let zigzag      = true;

    // So we perform a normal iterative level order traversal.
    while (queue.length) {

        // This will be our row, it will store all the nodes for the row in the tree
        let row       = [];
        let queue_len = queue.length;

        // So we're always going to invert the order of the rows.
        // We do this to create our zig zag effect.
        // Back, forward, back, forward, etc.
        zigzag = !zigzag;

        // We're going to get everything in the queue.
        // at this particular moment and nothing more.
        for (let counter = 0; counter < queue_len; counter++) {

            // Grab the current node by removing it off the end of the queue
            let node = queue.pop();

            // So, if the invert flag is set, we're going to push the current node
            // to the START of the row. Which means, we will produce a zig zag effect.
            // Without having to change the order in which we visit our nodes.
            // If the invert flag is not set, we're going to push the current node
            // to the end of the row stack like we normally would in level order traversal.
            if (zigzag) {
                row.unshift(node.val);
            } else {
                row.push(node.val);
            }

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

        // Push to the level_order array.
        level_order.push(row);
    }

    // Return the level_order array.
    return level_order;
};