BST의 유효성 확인

이 글은 랜덤 DS/Algo 시리즈의 첫 번째 글입니다.본 시리즈의 목적은 내가 해결한 DS/Algo 문제를 무작위로 수집하여 장래에 내가 인터넷에서 사람들에게 설명한 내용을 복습할 수 있도록 하는 것이다🤷‍♂️.

이것은 내가 면접 전에 자주 연습하는 문제 중의 하나다.

leetcode의 질문은 다음과 같습니다. -

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.

나는 우리가 BST를 검증하는 데 도움을 줄 수 있는 세 가지 실현이 있다는 것을 안다.

추가 공간을 가진 질서정연한 스트리밍

BST의 뚜렷한 특징은 같은 노드를 순서대로 옮겨다니면 순서대로 노드 값을 얻을 수 있다는 것이다.

function isValidBST(root){
 const arr = [];
 helper(root,arr);
 for(let index = 0;index<arr.length-1;index++){
        if(arr[index+1]<=arr[index]){
            return false;
        }
  }
    return true;
}

function helper(root,arr){
    if(!root)
        return;
    helper(root.left,arr);
    arr.push(root.val);
    helper(root.right,arr);
}

방법분해:-

초기화 공수조 arr.

내부 기능은 다음과 같습니다. -

은 BST를 순차적으로 통과합니다.

은 각 helper(root,arr)을 root.val으로 밀어 넣습니다.

그리고 우리는 arr을 순환한다. 어떤 색인에 대해서도 원소가 이전 원소보다 작거나 같으면 우리는 arr만 되돌려준다.이것은 원소가 엄격하게 요구에 따라 증가해야 하기 때문이다.

그렇지 않으면 false으로 돌아갑니다.

추가 공간이 필요 없는 질서정연한 스트리밍

잘못된 BST가 있는 경우 위 작업을 수행하고 true 공간을 추가로 사용하지 않고도 조기 종료할 수 있습니다.

var isValidBST = function(root){
    const prev = helper(root,null);
    return prev.isNotValid ? false : true;
    }

function helper(root,prev){
    if(!root)
        return prev;
    prev = helper(root.left,prev);
    if(prev && root.val <= prev.val){
        prev.isNotValid = true;
    }
    if(prev?.isNotValid)
       return prev;
    prev = root;
    prev = helper(root.right,prev);
    return prev;
}

방법분해:-

은 먼저 arr(helper(root,prev)은 이전 노드를 나타냅니다): -

prev - if(!root) return prev이 root이면 undefined 요소로 돌아갑니다.

prev - 각 prev = helper(root.left,prev)의 왼쪽 트리를 먼저 살펴보겠습니다.root원소.

prev - 왼쪽 트리에서 돌아오면 if(prev && root.val <= prev.val){ prev.isNotValid = true; }이 존재하면 prev과 root.val을 비교하여 현재 prev.val이 root.val보다 작거나 같은지 확인합니다.만약에 prev.val에 prev이라는 속성을 만들고 isNotValid으로 설정합니다.

true - if(prev?.isNotValid) return prev;의 존재 여부와 존재 여부를 확인합니다.
그러면 우리는 prev.isNotValid으로 돌아가 조기 퇴출을 하고 후속 우회전을 계속하지 않는가
자수

prev - 다음 노드에서 prev = root 값을 prev으로 설정하는 방법입니다.
이 root값을 사용하여 필요한 비교를 할 수 있다.

prev - 각 prev = helper(root.right,prev);의 올바른 하위 트리를 찾아root원소.

prev - 값을 반영하기 위해 return prev;을 호출 함수로 되돌려야 합니다.

prev - const prev = helper(root,null); 내부에서isValidBST .

prev - helper(root,null)이 존재하면 BST가 무효임을 의미합니다. 우리는 return prev.isNotValid ? false : true;으로 돌아가고 그렇지 않으면 prev.isNotValid으로 돌아갑니다.

BST 속성 활용

BST에서는 각 노드의 값이 왼쪽 조상보다 크고 오른쪽 조상보다 작아 유효하다고 할 수 있습니다.우리가 지금 쓸 것은: -

var isValidBST = function(root){
       return helper(root,-Infinity,Infinity);
   }
function helper(root,leftMax,rightMax){
    if(!root)
        return true;
    if(root.val > leftMax && root.val < rightMax) {
        return helper(root.left,leftMax,root.val) && helper(root.right,root.val,rightMax);
    }
    return false;
}

방법분해:-

false:

true - helper(root,prev)이 if(!root) return true;이면 BST라고 할 수 있습니다.
유효기간은 현재까지다.

root - undefined, if(root.val > leftMax && root.val < rightMax) { return helper(root.left,leftMax,root.val) && helper(root.right,root.val,rightMax); }과 root.val을 비교하는 핵심 논리입니다.leftMax이 rightMax보다 크고 root.val이 leftMax보다 작을 때만 우리는 상응하는 왼쪽 나무와 오른쪽 나무를 더욱 검사할 수 있고 두 개의 나무 모두 root.val으로 돌아가도록 요구해야 BST가 효과적이다.왼쪽 트리의 경우 rightMax이 현재 true으로, 오른쪽 트리의 경우 rightMax이 현재 root.val으로 변경됩니다.

만약에 상술한 조건이 실패한다면 우리는 그 어떠한 후속적인 왼쪽 또는 오른쪽 나무도 더 이상 검사할 필요가 없다는 것을 알고 leftMax으로 돌아가기만 하면 된다.

은 root.val 내부에서 false을 실행하고 isValidBST을 return helper(root,-Infinity,Infinity);으로 전달하며 leftMax을 -Infinity으로 전달하고 rightMax을 Infinity 노드의 초기값으로 전달한다.

모든 방법 중 마지막은 매우 깨끗해서 면접관이 그것을 기대할 수 있을 것이라고 나는 생각한다.나는 몇 가지 면접을 봤는데 첫 번째 방법은 이미 충분했고 면접관은 어떠한 최적화도 요구하지 않았다.만약 그들이 이렇게 한다면 나는 두 번째를 뛰어넘고 세 번째를 뛰어넘을 것이다.
그 밖에 귀환으로 인해 저는 창고가 차지하는 공간을 소홀히 했습니다. 만약 제가 필요하다고 생각한다면 앞으로 더 많은 방법으로 본문을 업데이트할 것입니다.

시간 내주셔서 감사합니다.