문제 :
https://leetcode.com/problems/validate-binary-search-tree/
예시 :
Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.
주어진 input이 이진트리인지 확인하는 문제
일단 드는 생각은 input 배열을 돌면서 루트에 대해 left, right가 null이 아니게 있는지 확인하면 될거 같다.
(+ 각 루트 노드 돌면서 왼쪽값 < 루트값 < 오른쪽 값 크기 순을 유지해야 한다)
근데 문제가 TreeNode 구조체를 이용하도록 되어있어서 일단 거부감이 든다 .. 겁 먹지 말자 !!
recursive하게와 DFS하게 풀면 될거 같다는 생각은 들었는데 접근을 어떻게 해야 할지 우선 차근 차근 생각해보자
1) DFS
class Solution {
public:
void helper(TreeNode* root, vector<int> &inorder){
if(root == nullptr){
return;
}
helper(root->left, inorder);
inorder.push_back(root->val);
helper(root->right, inorder);
}
bool isValidBST(TreeNode* root) {
vector<int> inorder;
helper(root, inorder);
for(int i= 1; i < inorder.size(); i++){
if(inorder[i-1] >= inorder[i]){
return false;
}
}
return true;
}
};
inorder 순으로 node들을 담는다. 담는 함수 helper는 재귀로 하여 inorder순을 유지한다.
isValid에서 이를 하나 하나 돌며 값 비교 하여 이진 트리인지 확인한다.
2) Recursive
class Solution {
public:
TreeNode* previous = nullptr;
//recursive
bool isValidBST(TreeNode* root) {
if(root == nullptr){
return true;
}
if (!isValidBST(root->left)) {
return false;
}
if (previous && previous->val >= root->val) {
return false;
}
previous = root;
return isValidBST(root->right);
}
}
previous는 위의 inorder와 같은 역할을 한다. previous가 만들어지고 나서야 3번째 if문을 들어설 수 있다. for문을 통해 inorder의 값의 크기를 비교했던 것 처럼 if문과 같은 역할을 하는데 false되지 않으면 마지막으로 right 값까지 비교를 다 마친 후 종료하게 된다.
메모리 효율도는 비슷하지만 run time은 위의 코드가 조금 더 앞섰다 ..! ! 둘다 하지만 재귀를 기반으로 한다는 점에서 비슷한 거 같다.
'Algorithm🐰 > 리트코드' 카테고리의 다른 글
[리트코드] 238. Product of Array Except Self (0) | 2021.12.10 |
---|---|
[리트코드] 76. Minimum Window Substring (슬라이딩 윈도우) (0) | 2021.08.05 |
[리트코드] 3. Longest Substring Without Repeating Characters (0) | 2021.07.16 |
[리트코드] 1. Two Sum (두수의 합) (0) | 2021.07.12 |
댓글