0098- 검증 두 갈래 검색 트리

인증 두 갈래 검색 트리

시나리오 1

초기화할 때 시스템의 최대값과 최소값을 가지고 귀속 과정에서 그들의 노드 값으로 바꿉니다. long으로 int를 대체하는 것은 int의 경계 조건을 포함하기 위한 것입니다

C++ - 소스 코드

#include 
#include 
#include 

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        
        //  
        return isValidBST(root, LONG_MIN, LONG_MAX);
    }
    
    bool isValidBST(TreeNode *root, long min, long max) {
        
        if (!root) {
            
            return true;
        }
        
        if (root->val <= min || root->val >= max) {
            
            return false;
        }
        
        //  
        return isValidBST(root->left, min, root->val) && isValidBST(root->right, root->val, max);
    }
};

방안 2

등호를 없애는 조건은 이런 제한 조건을 없애는 것과 같다.다음은 우리가 중서열을 사용하여 역대로 하는 방법을 살펴보자. 이런 방법은 사고방식이 매우 직접적이다. 중서열을 통해 모든 노드 값을 하나의 수조에 저장한 다음에 이 수조가 질서정연한지 아닌지를 판단한다.

C++ - 소스 코드

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        
        if (!root) {
            
            return true;
        }
        
        vector vals;
        inorder(root, vals);
        
        for (int i = 0; i < vals.size() - 1; ++i) {
            
            if (vals[i] >= vals[i + 1]) {
                
                return false;
            }
        }
        
        return true;
    }
    
    void inorder(TreeNode *root, vector& vals) {
        
        if (!root) {
            
            return;
        }
        
        inorder(root->left, vals);
        vals.push_back(root->val);
        inorder(root->right, vals);
    }
};

방안 3

반복적인 중순으로 훑어보지만, 다른 점은 훑어보는 결과를 하나의 수조에 저장하여 훑어보고 비교하지 않고, 새로운 노드를 훑어볼 때마다 이전 노드와 비교하고, 이전 노드보다 크지 않으면false를 되돌려주고, 모두 훑어보고true를 되돌려준다는 것이다

C++ - 소스 코드

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        
        TreeNode *pre = NULL;
        return inorder(root, pre);
    }
    
    bool inorder(TreeNode *node, TreeNode*& pre) {
        
        if (!node) {
            
            return true;
        }
        
        bool res = inorder(node->left, pre);
        if (!res) {
            
            return false;
        }
        
        if (pre) {
            
            if (node->val <= pre->val) {
                
                return false;
            }
        }
        
        pre = node;
        
        return inorder(node->right, pre);
    }
};

Grandyang 참조