[leetcode] Validate Binary Search Tree

유의할점

이진 검색 트리는 루트의 값이 왼쪽 값보다 크다. (같거나 크다가 아님.)

마찬가지로 루트의 값이 오른쪽 값보다 작다.

트리 문제는 재귀로 해결한다. 하지만 이진 검색 트리에서 왼쪽 오른쪽 크기만을 체크했다가는 틀릴수있다.

예를 들어 5 3 6 1 7 의 경우. 3의 오른쪽 자식이 7이다. 즉 3의 부모 5보다 크게 된다. 하지만 3은 5의 부분 트리로서 3의 자식은 7보다 작아야한다. 이 점에 유의해야한다.

풀이

전위 순회를 돌면서 root값을 배열에 저장하면 배열이 오름차순으로 정렬되어야한다.

왜냐면 이진탐색트리의 왼쪽은 루트보다 작고 오른쪽은 루트보다 크기 때문이다.

개선점 : 배열에 넣는 방식말고 따른 방식이 존재한다. 해당 코드는 아래 첨부

코드

C++ : 내가 푼 코드

/**
 * 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 {
private: vector<int> arr_;
    
public:
    void dfs(TreeNode* root){
        if(root==NULL)
            return;
        dfs(root->left);
        arr_.push_back(root->val);
        dfs(root->right);
    }
    
    
    bool isValidBST(TreeNode* root) {
        dfs(root);
        int arrSize = arr_.size();
        for(int i = 1; i < arrSize; i++)
            if(arr_[i-1]>=arr_[i])
                return false;
        return true;
    }
};

JAVA : 최대값, 최소값 지정

public class Solution {
    public boolean isValidBST(TreeNode root) {
        return helper(root, null, null);
    }
    
    boolean helper(TreeNode root, Integer min, Integer max) {
        if (root == null)
            return true;
        
        if ((min != null && root.val <= min) || (max != null && root.val >= max))
            return false;
        
        return helper(root.left, min, root.val) && helper(root.right, root.val, max);
    }
}

C++ : 루트에 대해서만 검증한다. 나머지는 재귀가 처리한다. 참조연산자를 사용해야 재귀가 이어진다.

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        TreeNode* prev = NULL;
        return validate(root, prev);
    }
    bool validate(TreeNode* node, TreeNode* &prev) {
        if (node == NULL) return true;
        if (!validate(node->left, prev)) return false;
        if (prev != NULL && prev->val >= node->val) return false; //전의 값이 현재값보다 작아야함.
        prev = node;
        return validate(node->right, prev);
    }
};