솔루션 개발:

질문

이 기사에서는 Leetcode '98. Validate Binary Search Tree' 질문을 다룰 것입니다. 이 질문은 보통 질문으로 평가됩니다.

의문:

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

예시:

Input: root = [2,1,3]
Output: true

질문 설명

이 질문의 등급은 보통입니다. 정확하다고 생각합니다. 이 질문은 Binary Search Trees 및 In order Tree Traversal 에 대해 배우기에 환상적입니다.

우리가 요청하는 것은 주어진 이진 검색 트리가 유효한지 여부를 확인하는 것입니다. 이진 검색 트리의 규칙을 준수한다는 의미입니다. 더 작은 값은 모두 왼쪽에 있고 더 큰 값은 모두 오른쪽에 있음을 의미합니다.

이 질문에 대한 많은 솔루션은 트리 전체에서 min 및 max 값에 초점을 맞추도록 합니다. 이것은 이 문제를 해결하기 위한 매우 일반적인 접근 방식입니다. 트리의 어느 곳에서나 최소값 또는 최대값이 위반되었는지 확인합니다. 이제 이것이 훌륭한 접근 방식이지만 문제를 해결하는 더 간단하고 더 나은 방법이라고 생각합니다.

내가 설명할 솔루션은 다른 많은 문제에 대한 지식을 이전할 수 있습니다.

99. Recover Binary Search Tree

권장 지식

Binary Tree

Depth First Search

In-order traversal

Binary Search Tree

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

이진 검색 트리가 주어졌습니다. 유효할 수도 있고 아닐 수도 있습니다.

유효성을 검사해야 합니다.

항상 최소 2개의 노드가 됩니다.

어떻게 할 것인가:

기본적으로 우리가 하려는 것은 순서대로 이진 트리를 순회하는 것입니다. 이것이 의미하는 것은 우리가 방문하는 NEXT 노드가 항상 이전 노드보다 커야 한다는 것입니다. 그렇지 않은 경우 트리가 즉시 유효하지 않음을 알 수 있습니다.

flag를 true로 설정하면 이 플래그는 트리가 유효한지 여부를 알려주는 데 사용됩니다. 기본적으로 항상 유효합니다. 이전 노드보다 작은 노드를 찾을 때까지.

트리의 순차적 순회에서 이전 노드를 추적할 것이므로 이전 노드 포인터를 선언합니다.

순회의 각 지점에서 '현재 노드가 이전 노드보다 작습니까?'라고 묻고 트리의 순회를 수행합니다. 그렇다면 트리가 유효하지 않다는 것을 알 수 있습니다. 그래서 우리는 flag를 false로 설정했습니다.

불량 노드가 발견되지 않으면 트리가 유효하고 플래그가 변경되지 않은 것입니다.

빅오 표기법:

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

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

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

리트코드 결과:

제출 링크 참조:

런타임: 67ms, 이진 검색 트리 검증을 위한 JavaScript 온라인 제출의 94.56%보다 빠름

메모리 사용량: 46.8MB, 이진 검색 트리 검증을 위한 JavaScript 온라인 제출물의 22.46% 미만

해결책

var isValidBST = function (root) {
    // This is the flag that will be returned
    // In the event we find a node that violates the BST property, we inverted the flag.
    let is_bst_valid = true;

    // We will also be tracking the previous node.
    // This will be used to check if the current node is greater than the previous node.
    // As a valid BST, the previous node must be less than the current node.
    let prev_node = new TreeNode(-Infinity, null, null);

    // We will traverse the tree in-order.
    // As a BST traversed in-order would result in something akin to a sorted array.
    // [1,2,3,4,5,6,7,8,9]
    // In the event we see something like this:
    // [1,2,3,4,*99,6,7,8,9,10]
    // We know it's not a valid BST.
    const in_order_traverse = (node) => {

        // Empty tree. Base case.
        if (!node || !is_bst_valid) {
            return;
        }

        // Get my left nodes.
        in_order_traverse(node.left);

        // The in order section
        // Check if the current node is greater than the previous node.
        // If not, it's a invalid tree
        if (node.val <= prev_node.val) {
            is_bst_valid = false;
        }

        // Update the previous node.
        prev_node = node;
        in_order_traverse(node.right);
    };

    in_order_traverse(root);

    // Return the flag
    return is_bst_valid;
};