[Leetcode] 98. Validate Binary Search Tree

Identifying the Problem

이진트리를 탐색하며, 왼쪽 하위 트리로 갈수록 값이 작아지고, 오른쪽 하위 트리로 갈 수록 값이 커지는지 판단한다.

Input: root = [5,1,4,null,null,3,6] Output: false

Explanation: root 5의 오른쪽 노드 값이 4로 작아졌다.

Organizing thoughts

// 72 / 80 test cases passed.

class Solution {
public:
    bool isValidBST(TreeNode* root) 
    {
        if(!root) return true;
        //가장 마지막 null은 true로 리턴 (defalut)
        
        if(root->left && root->val <= root->left->val){cout<<"1\n"; return false;} 
        //주어진 조건과 반대가 되는 순간 false를 return
        //root->left, right가 null인 상태에서 val을 접근하면 오류가 나기 때문에
        //left,right가 null이 아니라는 조건을 추가했다.
        if(root->right && root->val >= root->right->val) {cout<<"2\n"; return false;} 
        
        
        return isValidBST(root->left) && isValidBST(root->right); //중위 순회
    }
};

 

Mistake

오른쪽 노드의 값의 왼쪽 노드의 값은 최초 root노드 보다는 작아야 한다.

root < root->right->left < root->right 이런 셈이다 (val은 편의상 생략)

https://leetcode.com/problems/validate-binary-search-tree/discuss/1176115/Why-is-546nullnull37-not-a-valid-BST

Answer Sourcecode

정답코드 출처

C++ simple recursive solution - LeetCode Discuss

## 전체적인 flow는 나와 유사하다.

left 검사 시에는 이전 값을 최대값으로 두고, 다음으로 넘겼고,

right 검사시에는 이전 값을 최소값으로 두어 다음을 넘긴다.

하지만 내가 실수한 왼쪽과 오른쪽의 세부적인 디테일을 이 코드에선 min과 max를 넘김으로 해결했다.

class Solution {
public:
    
    bool isValidBST(TreeNode* root) 
    {
        return isValidBST(root, NULL, NULL);
    }

    bool isValidBST(TreeNode* root, TreeNode* minNode, TreeNode* maxNode) 
    {
        if(!root) return true;
        if(minNode && root->val <= minNode->val || maxNode && root->val >= maxNode->val)
            return false;
        return isValidBST(root->left, minNode, root) && isValidBST(root->right, root, maxNode);
    }
};