[LeetCode] 98 - Validate Binary Search Tree

문제

• 링크: https://leetcode.com/problems/validate-binary-search-tree
• 난이도: Medium
• 태그: 배열, 투포인터, 정렬
• 결과: Time: 00 ms (100%), Space: 23.32 MB (8.76%)

풀이

/**
 * 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 isValidBST(TreeNode* root) {
        vector<int> v;
        v.reserve(1e4);
        
        solve(root, v);

        int len = v.size();
        for (int i = 0; i < len - 1; ++i)
        {
            if (v[i] >= v[i + 1])
            {
                return false;
            }
        }

        return true;
    }

    void solve(TreeNode* root, vector<int>& v)
    {
        if (root->left != nullptr)
        {
            solve(root->left, v);
        }

        v.push_back(root->val);

        if (root->right != nullptr)
        {
            solve(root->right, v);
        }
    }
};

BST를 중위 순회하면 정렬된 결과가 나오므로, std::sort로 정렬한 결과와 비교한다.

이 포스트는 달레 스터디(2주차)에서 진행한 Blind 75 문제집 풀이의 일부입니다.