99. 이진 검색 트리 복구 🚀

솔루션 개발:

질문

Leetcode '99. Recover Binary Search Tree' 질문을 다루겠습니다. 이 질문은 보통 질문으로 평가됩니다.

의문:

You are given the root of a binary search tree (BST), where the values of exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.

예시:

Input: root = [1,3,null,null,2]
Output: [3,1,null,null,2]
Explanation: 3 cannot be a left child of 1 because 3 > 1. Swapping 1 and 3 makes the BST valid.

질문 설명

이 질문의 등급은 보통입니다. 나는 그것이 어려운 질문이라고 생각하지 않지만. 확실히 쉬운 질문도 아니고 평균적인 중간 질문도 아닙니다.

나는 며칠 동안이 질문에 갇혀 있었기 때문에 이것을 말합니다 (의사 코드 솔루션을 사용하더라도). 나중에 이 질문을 해결하기 위해 여러 번 시도했지만 실패했습니다.

질문을 이해할 만큼 이진 검색 트리를 잘 이해하지 못했다고 생각합니다. 나는 BST를 받았고 두 개의 노드가 교체되었다는 말을 들었습니다. 나는 노드의 값을 교환할 수 있고 그러면 트리가 유효할 것이라고 들었습니다. 하지만 솔직히 2개의 유효하지 않은 노드를 감지한 다음 다시 교체하는 방법을 이해하지 못했습니다.

Depth First Search In-Order 순회를 이진 검색 트리에 결합하면 정렬된 순서로 값 배열을 제공해야 합니다. 이 문제를 파악하고 나니 이 문제를 해결할 수 있었습니다.

권장 지식

Binary Tree

Depth First Search

In-order traversal

Binary Search Tree

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

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

이진 검색 트리의 노드 중 2개가 서로 바뀐 것을 알고 있습니다.

우리는 노드의 값을 교환할 수 있고 그러면 트리가 유효하다는 것을 알고 있습니다.

이진 검색 트리에 대한 깊이 우선 검색 순회를 사용하여 정렬된 순서로 값 배열을 얻을 수 있다는 것을 알고 있습니다.

어떻게 할 것인가:

기본적으로 우리가 하려는 것은 순서대로 이진 트리를 순회하는 것입니다. 이것이 의미하는 것은 우리가 방문하는 NEXT 노드가 항상 이전 노드보다 커야 한다는 것입니다. 그렇지 않은 경우 교환된 노드 중 하나를 찾은 것입니다.

첫 번째 교환된 노드를 감지하면 bad_node_1 라는 변수에 저장합니다. 이제 우리가 해야 할 일은 두 번째 불량 노드를 찾아 교체하는 것입니다. 따라서 이전과 동일한 논리를 적용하여 다음 노드를 이전 노드 값과 비교하여 이전 노드보다 큰지 작은지 확인합니다. 현재 노드가 이전 노드보다 작은 것을 감지하면 두 번째 불량 노드를 찾은 것입니다. 그런 다음 bad_node_2라는 변수에 저장합니다.

그런 다음 단순히 values 를 교체하십시오. 이것이 우리 논리의 끝입니다.

빅오 표기법:

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

공간 복잡도: O(h) | 여기서 h는 이진 검색 트리의 높이 | Call Stack 때문에 in-order traversal 안에 트리의 높이를 저장할 것이기 때문입니다.

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

리트코드 결과:

제출 링크 참조:

런타임: 128ms, 이진 검색 트리 복구에 대한 JavaScript 온라인 제출의 96.39%보다 빠름.

메모리 사용량: 52.8MB, 이진 검색 트리 복구를 위한 JavaScript 온라인 제출물의 12.17% 미만.

해결책

var recoverTree = function (root) {

    /* -------------------------------------------------------------------------- */
    /*                       99. Recover Binary Search Tree                       */
    /* -------------------------------------------------------------------------- */

    /**
     * @author  Samuel Hinchliffe
     * @see    {@link linkedin.com/in/samuel-hinchliffe-🚀-2bb5801a5/ | Author's Linkedin }
     * @see    {@link github.com/Samuel-Hinchliffe}
     */

    /* ----------------------------- Solution Below ----------------------------- */

    // Our bad nodes (We will swap them later)
    let bad_node_1 = null;
    let bad_node_2 = null;

    // A prev_node node to help us keep track of
    // the last node we visited.
    // We set it as a dummy node
    let prev_node = new TreeNode(-Infinity, null, null);

    // The function that will find the 2 bad nodes
    const find_bad_nodes = (node) => {

        // Reached end of tree
        if (!node) {
            return null;
        }

        /* --------------- Perform In-Order Traversal --------------- */

        // Get all the left nodes
        find_bad_nodes(node.left);

        // Is the node less than the prev_node val?
        // And have we set bad_node_1 yet?
        if (bad_node_1 == null && prev_node.val >= node.val) {
            // Set the bad node to be the one behind it.
            bad_node_1 = prev_node;
        }

        // Is the node less than the prev_node val?
        // and have we set bad_node_1 yet?
        if (bad_node_1 != null && prev_node.val >= node.val) {
            // Set the bad node to the current node
            bad_node_2 = node;
        }

        // Update our prev_nodes node pointer
        prev_node = node;

        // Get all the right nodes
        find_bad_nodes(node.right);
    };

    // FIND THOSE BAD NODES!!!
    find_bad_nodes(root, prev_node);

    // We have found the bad nodes, now swap them

    // Swap the values of the bad nodes
    let temp = bad_node_1.val;
    bad_node_1.val = bad_node_2.val;
    bad_node_2.val = temp;
};