Leetcode - 98. Validate Binary Search Tree

문제

주어진 트리가 BST(Binary Search Tree)를 만족하는지 확인하라

• left 자식트리의 모든 노드 값이 루트노드 보다 작아야한다.
• right 자식트리의 모든 노드 값이 루트노드 보다 커야한다.
• left, right 의 subtree 모두 BST를 만족한다.

해결 O(n) / O(2n)

정렬된 트리이니, Inorder 트리 순회를 하면서 값을 vector에 push_back(). vector의 마지막 값이 현재 노드의 값보다 크면 BST를 만족하지 못함. 문제는 공간복잡도가 콜스택 O(n)에 추가로 vector O(n)이다.

class Solution {
    bool inorder(TreeNode* root, vector<int> &arr) {
        if (root == NULL)
            return true;
        if (!inorder(root->left, arr))
            return false;
        //cout << root->val << " ";
        if (!arr.empty() && arr.back() >= root->val)
            return false;
        arr.push_back(root->val);
        if (!inorder(root->right, arr))
            return false;
        return true;
    }
public:
    bool isValidBST(TreeNode* root) {
        vector<int> arr;
        return inorder(root, arr);
    }
};

해결 O(n)/ O(n)

생각해보면 vector에 모든 값을 저장할 필요가 없음. prev변수 하나만 비교해도됨. 아래와 같이 코드 개선. 공간복잡도는 콜스택 O(n) 만 사용.

class Solution {
    TreeNode* prev = NULL;
    bool inorder(TreeNode* root) {
        if (root == NULL)
            return true;
        if (!inorder(root->left))
            return false;
        /* inorder traval */
        if (prev && prev->val >= root->val)
            return false;
        prev = root;
        return inorder(root->right);
    }
public:
    bool isValidBST(TreeNode* root) {
        return inorder(root);
    }
};