솔루션 개발:

질문

이 기사에서는 Leetcode '226. Invert Binary Tree' 질문을 다룰 것입니다. 이 질문은 쉬운 질문으로 평가됩니다.

의문:

Given the root of a binary tree, invert the tree, and return its root.

예시:

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

질문 설명

이진 트리를 반전해야 합니다. 마치 거울을 나무에 대고 있는 것처럼.
이것이 의미하는 바는 node마다 left 및 right 노드를 교환해야 한다는 것입니다. 노드가 더 이상 남지 않을 때까지 계속합니다.

따라서 트리 맨 아래부터 시작하여 left 노드를 right 노드로 교환하고 그 반대의 경우도 마찬가지입니다.

권장 지식

Binary Trees

Post Order Travel

Array Destructuring. (ES6) (Optional)

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

트리가 있고 이를 반전시켜야 합니다. 즉, left 노드는 right 노드가 되고 right 노드는 left 노드가 됩니다.

어떻게 할 것인가:

Post Order Traversal을 사용하여 tree를 반전시킬 것입니다. 즉, 트리의 왼쪽 맨 아래에서 시작하여 트리의 root까지 다시 작업합니다.

그런 다음 left 및 right 노드를 교환합니다. root 노드에 다시 도달할 때까지 트리의 모든 노드에 이 작업을 수행합니다.

재귀적으로 진행할 때 이동하는 모든 노드에서 왼쪽 노드와 오른쪽 노드를 교환하기만 하면 됩니다.

먼저 노드가 존재하는지 확인하여 이를 수행합니다. 이것은 엣지 케이스와 트리의 끝에 도달했을 때를 위한 것입니다.

왼쪽 노드를 유지하기 위해 임시 변수를 선언합니다(재정의하려고 하지만 나중을 위해 여전히 필요하므로).

그런 다음 왼쪽 노드와 오른쪽 노드를 교환합니다. 해당 임시 변수의 도움으로.

그런 다음 지정된 트리의 모든 왼쪽 노드에 대해 이 작업을 수행한 다음 지정된 트리의 모든 오른쪽 노드에 대해 수행합니다. 이 부품의 순서는 중요하지 않으며 교체만 하면 됩니다.

왼쪽 노드와 오른쪽 노드를 교체했다고 가정하고 루트 노드를 반환합니다. 이 함수를 재귀적으로 호출할 것이기 때문에 이렇게 합니다. 그래서 우리는 스택에서 다시 올라갈 수 있습니다. 그러나 이것은 스택의 마지막 노드에 도달했을 때 가장 중요합니다.

빅오 표기법:

시간 복잡도: O(n) | 여기서 n은 트리 노드 수 | 우리는 각 노드를 통과하기 때문입니다.

공간 복잡도: O(h) | 여기서 h는 트리의 최대 높이 | 그것이 호출 스택의 크기이기 때문에 | 호출 스택이 ENTIRE 트리만큼 깊을 가능성이 있는 최악의 경우이므로 O(n)이라고 주장할 수 있습니다.

' 개선될 수 있을까? ' 예! Morris Traversal은 O(1) 공간 복잡성에서 이 문제를 해결할 수 있습니다. 그러나 Morris Traversal은 읽기 까다롭고 어렵습니다. 단순화를 위해 여기서는 사용하지 않습니다.

리트코드 결과:

제출 링크 참조:

런타임: 61ms, Invert Binary Tree에 대한 JavaScript 온라인 제출의 87.47%보다 빠름.

메모리 사용량: 47MB, Invert Binary Tree에 대한 JavaScript 온라인 제출물의 40.24% 미만.

솔루션 1

    var invertTree = function (root) {
    /* -------------------------------------------------------------------------- */
    /*                           226. Invert Binary Tree                          */
    /* -------------------------------------------------------------------------- */

    // We have reached a leaf node, so we need to bubble back up the stack.
    // To the next node.
    if (!root) {
        return root;
    }

    // A temporary variable to hold the left node (As we're about to override it but still need it for later).
    let temp_node = root.left;

    // We then swap the left and right nodes. With the help of that temporary variable.
    root.left  = root.right;
    root.right = temp_node;

    // We then do this for all the left nodes of the given tree, and then all the right nodes of a given tree.
    invertTree(root.left);
    invertTree(root.right);

    // Assuming we have swapped our left and right nodes, we return the root node.
    return root;
};

솔루션 2

 var invertTree = function (root) {

    // We have reached a leaf node, so we need to bubble back up the stack.
    // To the next node.
    if (!root) {
        return root;
    }

    // ES6 Destructuring.
    // What this does is take the left and right nodes and swap them.
    // But without the need of a temp variable. As in object destructuring, it remembers.
    // Although, if you're a performance fanatic, this isn't efficient. 
    [root.left, root.right] = [invertTree(root.right), invertTree(root.left)]

    return root
};