[알고리즘] 8 - 유효한 이진 검색 트리

Link for the problem

Link for the solution

이것은 가장 어려운 BST 문제는 아니지만 BST 구조의 개념을 이해하는 데 정말 좋습니다.

잘못된 접근

처음 문제를 보았을 때, 나는 단순히 부모 노드와 그것의 좌우 노드를 재귀로 비교하려고 했습니다. 모든 부모가 왼쪽보다 크고 오른쪽보다 작은지 재귀적으로 확인하고 있기 때문에 결국 재귀를 사용하여 답을 줄 것이라고 생각했습니다.

내가 저지른 실수

여기서 내가 저지른 실수(아마도 이 문제를 해결하려고 시도한 99%의 사람들이 같은 문제에 직면했을 것임)는 각 하위 트리가 유효한지 확인하는 것뿐이라는 것입니다. BST의 모든 하위 트리가 유효한 BST인 경우 전체 트리가 유효한 BST라는 것이 사실처럼 들리기 때문에 이상합니다. 하지만
다음 예를 보십시오.
잘못된 BST - 3과 4는 5의 오른쪽 트리에 있을 수 없습니다.


이 예에서는 모든 하위 트리가 유효합니다. 그러나 전체 BST는 유효하지 않습니다. 따라서 트리가 유효한 BST인지 확인하기 위해 추가 조치가 필요합니다. 하지만 우리는 어떻게 해야 합니까?

해결책

모든 하위 트리가 유효한지 확인하는 것이 답으로 이어지지 않는 이유부터 시작하겠습니다. 그 이유는 각 검사에서 이전 결과를 고려하지 않기 때문입니다. 그렇다면 추적해야 할 이전 결과는 무엇입니까? 최소 및 최대 경계.

예를 들어,

      (10)
     /    \
   (7)    (17)
   /\      /\
 (4)(9)  (11)(18)
    /\
  (1)(?)

채울 수 있는 값(?)을 생각해 봅시다.
=> [10,11,12,13...]
값이 9보다 엄격하게 커야 한다고 말할 수 있기 때문입니다.

하지만 값이 10인 루트 노드의 왼쪽에 있는 (?) 때문에 모든 (?)가 10보다 작아야 한다는 사실을 고려하면 채울 수 있는 숫자가 없음을 알 수 있습니다. 공백.

이제 더 명확해 보이지만 한 가지 더 알아봐야 합니다. 언제 최대 경계를 얻습니까?

루트 노드부터 시작하겠습니다. 우리는 루트 노드의 왼쪽 트리 내부의 모든 노드가 10보다 작아야 함을 볼 수 있습니다. 따라서 10 아래의 모든 왼쪽 노드는 최대 경계가 10이 됩니다. 반면에 루트 노드의 오른쪽 트리 내부의 모든 노드는 다음을 갖습니다. 10보다 커야 합니다.

왼쪽 트리 노드 => [...8,9]
오른쪽 트리 노드 => [11, 12, ...]

따라서 왼쪽 자식으로 이동할 때마다 최대 경계가 설정되고 오른쪽 자식으로 이동할 때마다 최소 경계가 설정되는 것을 볼 수 있습니다.

내 솔루션

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        // The idea for the solution:
        //      Need to set the minimum and maximum boundary
        //      1. Left node cannot be greater than the current node
        //      2. Right node cannot be smaller than the current node
        //      3. If the node is left, maximum boundary will be set up.
        //      4. If the node is right, minimum boundary will be set up.
        return helper(root, LONG_MIN, LONG_MAX);
    }

    bool helper(TreeNode* root, long long int minVal, long long int maxVal){

        // Base case
        if(!root)return true;

        // within the range of minval and maxval
        if(root->val <= minVal || root->val >= maxVal)return false;

        // root->left => should be less than root->val
        if(root->left && root->left->val >= root->val) return false;

        // root->right => should be greater than root->val
        if(root->right && root->right->val <= root->val) return false;

        // Should update the left node restriction
        return (helper(root->left, minVal, root->val) && helper(root->right, root->val, maxVal));
    }
};