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

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

 

주어진 tree가 유효한 이진 트리인지 판단하라.

 

우선 이진 트리에 조건을 생각해 볼 필요가 있다.

 

위 그림처럼, node값은 늘, left 와 right 의 사이 값을 가져야 한다.

이 문제가 child 가 생기면 복잡해 진다. 

위 그림처럼, 노드에서 조건을 만족해도 전체 트리에서는 만족하지 않게 될 수 있다. 

즉, 정리하면 특정 노드 기준으로 

left node 중 최대값, right node 중 최소값 사이에 노드값이 존재해야 한다.

 

따라서 

특정 노드에서 모든 차일드 노드를 순회해서 left의 최대값, right의 최소값 을 구한 후 

현재 노드가 이 값 사이에 있나 확인한다. 

이 검색을 모든 노드로 확장한다. 

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;
        if (!isValidBST_BT(node->left))
            return false;
    }
    if (node->right != NULL)
    {
        if (getLeftLeaf_BT(node->right) <= node->val)	
            return false;
        if (!isValidBST_BT(node->right))
            return false;
    }
    return true;
}

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

하지만 이 방법은 TC가 O(NxN) 으로 최적화 필요하다.  

 

조금 복잡하지만, 

노드 1회 방문 시 차일드에서 바로 최대, 최소 정보를 얻어서 유효성 검사를 한다.

pair<bool, pair<int, int>> isValidBSTHelper(TreeNode* node)
{
    const auto NULL_PAIR = make_pair(0, 0);
    if (node == nullptr)
        return make_pair(true, NULL_PAIR);

    if (node->left == nullptr && node->right == nullptr)
    {
        return make_pair(true, make_pair(node->val, node->val));
    }
    else if (node->left != nullptr && node->right == nullptr)
    {
        auto leftV = isValidBSTHelper(node->left);
        if(!leftV.first)	return make_pair(false, NULL_PAIR);

        if(leftV.second.second >= node->val)
            return make_pair(false, NULL_PAIR);

        return make_pair(true, make_pair(leftV.second.first, node->val));
    }
    else if (node->left == nullptr && node->right != nullptr)
    {
        auto rightV = isValidBSTHelper(node->right);
        if (!rightV.first)	return make_pair(false, NULL_PAIR);

        if (rightV.second.first <= node->val)
            return make_pair(false, NULL_PAIR);

        return make_pair(true, make_pair(node->val, rightV.second.second));
    }
    else
    {
        auto leftV = isValidBSTHelper(node->left);
        auto rightV = isValidBSTHelper(node->right);
        if (!leftV.first || !rightV.first)	
            return make_pair(false, NULL_PAIR);

        if (leftV.second.second >= node->val || rightV.second.first <= node->val)
            return make_pair(false, NULL_PAIR);

        return make_pair(true, make_pair(leftV.second.first, rightV.second.second));
    }
}

bool isValidBST(TreeNode* root) 
{
    auto ret = isValidBSTHelper(root);
    if (ret.first == false)
        return false;

    return true;
}

이 방법은 O(N)으로 적절하지만, 로직이 생각보다 복잡하다. 

 

 

다른 답을 찾아보니, 접근을 다르게 했다. 

 

InOrder 풀이를 확인해 보자.

InOrder 탐색이라 함은, left node, self, right node 순으로 탐색 한다는 것이다. 

하지만 selft의 parent입장에서 본다면 마지막 방문한 노드는 무엇일까? 

child가 left 일때는 child의 right end node. 

child가 right 일때는 parent node가 child node보다 먼저 방문된다. 

 

정리하면, 이것이 의미하는 바는 이렇다. 

특정 노드를 기준으로 단지 현재 노드가 마지막 방문한 이전 노드값보다 큰지 만을 확인하는데, 

마지막 방문 노드는 현재 노드의 왼쪽 편의 제일 큰 값이 된다. 

(이것을 Inorder 탐색이 가능하게 해 준다.)

 

모든 노드에 대하여 위 조건이 만족하면 

이진 트리 조건을 만족한다고 할 수 있나? 

그렇다. 

 

코드 

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

    if (!isValidBSTHelper(node->left, minV))
        return false;

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

    if (!isValidBSTHelper(node->right, minV))
        return false;

    return true;
}

bool isValidBST(TreeNode* root) 
{
    long minV = LONG_MIN;
    return isValidBSTHelper(root, minV);
}

 

 

결과.