98. Validate Binary Search Tree

 이진 트리가 유효한 이진 탐색 트리(Binary Search Tree, BST)인지 판별하는 것입니다.


노드의 왼쪽 서브트리에는 노드의 키보다 작은 키를 가진 노드만 포함되어 있습니다.
노드의 오른쪽 서브트리에는 노드의 키보다 큰 키를 가진 노드만 포함되어 있습니다.
왼쪽과 오른쪽 서브트리 모두 이진 탐색 트리여야 합니다.

예시 1: 입력: root = [2,1,3], 출력: true
예시 2: 입력: root = [5,1,4,null,null,3,6], 출력: false. 설명: 루트 노드의 값은 5이지만, 그 오른쪽 자식 노드의 값은 4입니다.

트리의 노드 수는 범위 [1, 10^4] 내에 있습니다.
노드의 값은 -2^31 <= Node.val <= 2^31 - 1 범위 내에 있습니다.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public bool IsValidBST(TreeNode root) {
        return IsValid(root,long.MinValue,long.MaxValue);
    }
    public bool IsValid(TreeNode T,long min,long max){
        if(T == null) return true;
        if(T.val <= min || T.val >= max) return false;
        return IsValid(T.left,min,T.val) && IsValid(T.right,T.val,max); 
    }
}

각 노드가 유효한 범위 내에 있는지 확인해야 합니다. 

루트 노드는 모든 정수 값을 가질 수 있으므로 최소값과 최대값을 각각 long.MinValue와 long.MaxValue로 설정합니다. 

그런 다음 각 노드에서 왼쪽 서브트리를 검사할 때는 최대값을 현재 노드의 값으로 업데이트하고, 

오른쪽 서브트리를 검사할 때는 최소값을 현재 노드의 값으로 업데이트합니다.