[LeetCode C++] 98. Validate Binary Search Tree

⭐️ 난이도

Medium

 

---

⭐️ 문제

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

Validate Binary Search Tree - LeetCode

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

이진 트리의 루트가 주어졌을 때, 그것이 유효한 BST인지 검사하시오.

 

A valid BST is defined as follows:

유효한 BST는 다음과 같이 정의된다.

 

1. The left subtree of a node contains only nodes with keys less than the node's key.

   왼쪽 서브트리는 노드의 키보다 작아야 한다.

2. The right subtree of a node contains only nodes with keys greater than the node's key.

   오른쪽 서브트리는 노드의 키보다 커야 한다.

3. Both the left and right subtrees must also be binary search trees.

   왼쪽, 오른쪽 서브트리 모두 BST여야 한다.

 

 

---

⭐️ Follow-up

 

X

 

---

⭐️ Idea flow

 

맨 처음에 설계했던 방법은 현재의 노드의 왼쪽 서브트리의 값, 오른쪽 서브트리의 값을 각각 비교하여 주어진 조건에 맞는지 확인하려 했다.

결론적으로는 이런 방법을 사용하면 안됐다.

 

루트 노드의 값을 기준으로 노드가 배정되어야 하는데, 위와 같은 방법을 사용하면 예외가 발생할 수 있다.

ex) [5,4,6,null,null,3,7]

 

이를 해결하기 위해서는 해당 노드에 들어갈 수 있는 값의 범위를 전달해야 한다.

즉, 해당 노드에 들어갈 수 있는 최소값과 최대값을 설정한다.

이를 재귀적으로 반복하기 위해 매개 변수로 TreeNode* root, TreeNode* low, TreeNode* high를 전달한다.

(순서대로 현재의 노드, 현재 노드 값이 가질 수 있는 최소값, 현재 노드 값이 가질 수 있는 최대값)

 

어떤 노드 A가 있다고 가정하자.

A의 왼쪽 서브트리의 값이 가질 수 있는 최대 값은 (A->val) - 1이다. (왼쪽 서브트리는 루트보다 값이 작아야 하므로)

A의 오른쪽 서브트리의 값이 가질 수 있는 최소 값 또한 (A->val) - 1이다. (오른쪽 서브트리는 루트보다 값이 커야 하므로)

 

따라서 isValid(root->right, root, high)와 isValid(root->left, low, root)를 실행하여 둘 중 하나라도 return 값이 false면 해당 구조는 이진 트리가 아닐 것이다.

 

---

⭐️ Code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:

    // 현재 노드, 노드가 가져야하는 최소값, 노드가 가져야하는 최대값
    bool isValid(TreeNode* root, TreeNode* low, TreeNode* high) {
        if(!root)   return true;

        if(low && root->val <= low->val)    return false;
        if(high && root->val >= high->val)  return false;
        
        return isValid(root->right, root, high) && isValid(root->left, low, root);
    }
    
    bool isValidBST(TreeNode* root) {
        return isValid(root, nullptr, nullptr);
    }
};

 

 

---

⭐️ Feedback

 

이 문제를 해결 할 수 있는 방법으로 left와 right pointer를 재귀적으로 타고 들어가서 해결하는 방법만을 생각했는데,

다른 사람의 코드를 보니 inorder(중위 순회)로 해결하는 방법이 있었다.

 

inorder는 "left subtree 모두 방문 -> root 노드 방문 ->right subtree 모두 방문" 하는 순회 방법이다.

이진 트리의 특징을 생각해보면 제일 작은 수는 제일 left subtree(node)에 위치하고, 제일 큰 수는 제일 right subtree(node)에 위치한다.

그리고 중간 값은 항상 root에 위치한다.

 

따라서 inorder 순회 결과를 나열해보면 제일 작은 수부터 제일 큰 수까지 정렬이 되어 있을 것이다.

그럼 이 순회 결과를 vector 컨테이너에 따로 저장한 다음, i번째 요소의 값이 i-1번째 요소의 값보다 크거나 같다면 해당 구조는 유효한 이진 트리가 아닐 것이다.

 

 

[전체 코드 보기]

class Solution {
private:
    vector<int> tree;
    
public:
    void inOrder(TreeNode* root) {
        if (!root)
            return;
        inOrder(root->left);
        tree.emplace_back(root->val);
        inOrder(root->right);
    }
   
    bool isValidBST(TreeNode* root) {
        if (!root)
            return true;
        
        inOrder(root);
        for (int i=1; i<tree.size(); i++)
            if (tree[i] <= tree[i-1])
                return false;
        return true;
    }
};