[LeetCode] 98. Validate Binary Search Tree

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

Validate Binary Search Tree - LeetCode

 

이진 트리가 주어졌을때, 이 이진트리가 이진탐색트리인지 (왼쪽 자식노드들이 모두 부모노드보다 작고, 오른쪽 자식노드들은 모두 부모노드보다 큰지) 확인하는 문제다.

 

Vector를 하나 만들어 부모 노드부터 차례차례로 내려가면서 방문하는 노드마다 왼쪽인지 오른쪽인지와 해당 부모 노드의 값을 저장해준다. 왼쪽인 경우엔 (0, 노드값) 오른쪽일 경우엔 (1, 노드값)으로 pair를 만들어 저장해주었다.

그 후, vector를 순회하며 방문한 노드와 각각의 pair를 비교해줘 하나라도 false가 되면 return해주고, 끝까지 모든 자식노드에 도달하면 true를 return 해주었다.

 

코드는 아래와 같다.

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        vector<pair<int,int>> vec;
        return run(root, vec);
    }
    
    bool run(TreeNode * node, vector<pair<int,int>> vec) {
        for (int i=0; i<vec.size(); i++) if (vec[i].first==0 && node->val>=vec[i].second ||vec[i].first==1 && node->val<=vec[i].second) return false;
        bool l = true, r = true;
        if (node->left!=NULL) {
            vec.push_back(make_pair(0,node->val));
            l = run(node->left, vec);
            vec.erase(vec.begin()+vec.size()-1);
        } 
        if (node->right!=NULL) {
            vec.push_back(make_pair(1,node->val));
            r = run(node->right, vec);
            vec.erase(vec.begin()+vec.size()-1);
        }         
        return l&&r;
    }
};