[Binary Tree][Medium] 98. Validate Binary Search Tree

https://leetcode.com/problems/validate-binary-search-tree/description

 

Q. 입력된 tree가 유효한 binary search tree인지 판단하라. 

 

 

Solution. 

 우선 Binary Search Tree의 요건에 대해 생각해 보자. 

 특정 노드 기준으로 left side가 모두 해당 노드 값보다 작아야 한다. 

 right side는 모두 커야 한다.   

노드의 child가 하나 일 때는 비교적 간단하다. 

 

위 트리로 다시 확인해 보자.

 

6의 노드의 지점에서 보자면 간단하다. 

조건을 만족한다. 

 

그러나 위 노드를 root, 즉 5노드의 지점에서 다시 보자. 

이때는 left 전체의 최대값과, right 전체의 최소값을 해당 노드와 비교해야 한다. (그래서 만족하지 않는다.)

따라서 이 문제는 child 노드에서의 최대(left child 일때)와 최소(right child일때) 값을 구해야 판단이 된다는 것이다. 

 

특정 노드의 left side 최대 값은,  left child에서 우측 최하단 leaf node 일 것이다. 

right side의 최소값은 right child에서 왼쪽 최하단 leaf 노드 일 것이다. 

현재 노드가 이 값들 사이에 존재하면, 이 노드 기준 binary search 트리를 만족한다고 할 수 있겠다. 

 

이 처리를 모든 노드에서 한다. 

 

코드로 로직을 작성해 본다. 

 

int getLeftLeaf_BT(TreeNode* node)
{
    return node->left == NULL ? node->val : getLeftLeaf_BT(node->left);
}
int getRightLeaf_BT(TreeNode* node)
{
    return node->right == NULL ? node->val : getRightLeaf_BT(node->right);
}
bool isValidBST_BT(TreeNode* node)
{
    if (node == NULL)	return true;

    if (node->left != NULL)
    {
        // 왼쪽 최대값과 현재 값 비교.
        if (getRightLeaf_BT(node->left) >= node->val)	
            return false;
        // valid 한 child에 대해 같은 test 실시.
        if (!isValidBST_BT(node->left))
            return false;
    }
    if (node->right != NULL)
    {
        // 오른쪽 최소값과 현재 값 비교.
        if (getLeftLeaf_BT(node->right) <= node->val)	
            return false;
        // valid 한 child에 대해 같은 test 실시.
        if (!isValidBST_BT(node->right))
            return false;
    }
    return true;
}

bool isValidBST(TreeNode* root) 
{
    return isValidBST_BT(root);
}

 

적절한 결과를 얻었다. 

 

note) 생각보다 좋은 문제. 

 Binary Tree의 기본 조건을 알고 실제 구현 할 수 있어야 풀 수 있는 문제. 

 

 

 

=== Update. 

 

BST가 오름차순 정렬되어야 valid 한것에 착안, 

In Order Traverse를 활용한다. 

 

이전 traverse한 노드는 반드시 현재 노드보다 작아야 한다.

 

코드 .

 bool InOrderCheck(TreeNode* node, long long& leftMin)
{
    if(node == nullptr)
        return true;

    if(!InOrderCheck(node->left, leftMin))
        return false;

    if(leftMin >= node->val)
        return false;
    leftMin = node->val;

    if(!InOrderCheck(node->right, leftMin))
        return false;

    return true;
}

bool isValidBST(TreeNode* root) 
{
    long long lMin = LLONG_MIN;
    return InOrderCheck(root, lMin);
}

 

 

결과.