[C++] leetCode 문제풀이 기록 1

--------------------------기록 양식--------------------------
시간 (문제해석+풀이 정리까지) 00:00 / (코드 작성까지) 00:00
정답여부 O/X
내 풀이 자유서술
정답 자유서술
재시도(optional) 재시도한 풀이 또는 추후 재시도 시 유념할 것들

 

98. Validate Binary Search Tree

시간 2:17 / 10:38
정답여부 X
내 풀이 root 노드와 자식 노드의 값만 비교하면 된다고 생각했다.

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if (root==NULL) return true;

        TreeNode* left = root->left;
        TreeNode* right = root->right;

        bool leftValid = true;
        bool rightValid = true;
        
        if(left!=NULL) leftValid = root->val > left->val;
        if(right!=NULL) rightValid = root->val < right->val;

        return leftValid && rightValid && isValidBST(root->left) && isValidBST(root->right);
    }
};

정답 BST의 삽입이 어떤 과정을 따르는지 떠올려보자. 루트 노드에서 시작해서 삽입하려는 노드와 key를 비교한 뒤 점점 아래로 내려가는 구조다. 즉 하나의 자식 노드는 부모 노드뿐 아닌 조상 노드들에 의해 값의 범위를 제한받는다. 예를 들어 부모 노드 p가 4 < p < 8와 같은 범위에 존재해야 한다면 자식도 그 범위를 벗어날 수 없다.

즉 자식 노드는 부모 노드의 최소값과 최대값을 물려받는다.

 

재시도 순환 외의 풀이를 살펴볼 것.