98. Validate Binary Search Tree
    Medium

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.

Example 1:

Input: root = [2,1,3]
Output: true

Example 2:

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.

Constraints:

The number of nodes in the tree is in the range [1, 104].
-231 <= Node.val <= 231 - 1

문제 설명

이진 검색 트리 노드를 줄테니 Binary Search Tree가 맞는지 아닌지 검증하라 가 문제다.
BST 트리는 부모 노드 기준 왼쪽 자식 노드는 작아야 하고 오른쪽 자식 노드는 커야 한다. 이 법칙은 트리가 아래로 갈수록 계속 적용된다.
첫번째 트리 2,1,3 은 true이고, 두번째 트리는 leaf Node에 3 떄문에 false다. 3은 rootNode인 5보다 커야 한다.(우측에 있으니까)

이런 트리 특성에 맞추어 min, max 값을 계속 다른 값을 할당해 줌으로써 문제를 풀어야 한다.

난 이 문제를 못풀었던 이유가 1.루트 트리를 기준으로 좌/우 측 을 나눠 왼쪽 영역은 max가 rootNode보다 작도록 고정, 오른쪽 영역은 min = rootNode로 할당한후 전체 트리가 다 적용되도록 잘못 생각했다 -> 모든 노드마다 min or max값이 바뀐다. 왼쪽 자식 노드로 가면 max 값을 부모 노드 값으로, 오른쪽 자식 노드로 가면 min값을 부모노드 값으로 할당해야 한다.

2. min, max 변수를 전역 변수로 설정했는데
   
   위처럼 이렇게 정의하면 이런 문제에서 max,min을 전역으로 정의해버리면 안됨, 함수 파라미터로 넣어줘야 한다. 왜냐하면, 트리에서 -> 리프트리까지 한번 동작에서 max, min값이 사용된 값이 전역변수로 공유 되버리면 트리가 만약 레프트노드 에서 부모노드로 올라오고 라이트 노드로 내려갈때 min max 값을 left때 값으로 공유해버린다, 만약 파라미터로 넣어주면 right로 넘어갈때 left 자식node의 dsf 함수 콜 할때 min, max 값이 아니라 루트 노드의 min, max 값을 갖고 right로 가기 떔에 정상 작동한다. 즉 min, max값은 전역 X -> 파라미터 O

정답 코드는 아래와 같다

const root = new Node(
  5,
  new Node(4, null, null),
  new Node(6, new Node(3, null, null), new Node(7, null, null))
);

// console.log(root.left);

function isValidBST(root) {
  if (!root) {
    return true;
  }

  return dfsForValidBST(root, Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER);
}

/**핵심 포인트 : 트리에서 좌측으로 내려가면 최대값이 변하고, 우측으로 내려가면 최소값이 변한다.  */
function dfsForValidBST(node, min, max) {
  // base case for recursion. return false if current node does not adhere to min and max
  if (node.val <= min || node.val >= max) {
    return false;
  }

  //left 자식 노드가 있다면, dfs(node.left)로 자식노드를 넣어주고, 
  //트리에서 왼쪽으로 내려 가면 최대값이 변해야 하므로, 현 node.val을 max param에 넣어줘 최대값을 부모노드 값으로 변화시킨다.    
  if (node.left) {
    const isLeftValidBST = dfsForValidBST(node.left, min, node.val);
    if (!isLeftValidBST) {
      return false;
    }
  }

  //right 자식 노드가 있다면, dfs(node.right)로 자식노드를 넣어주고, 
  //트리에서 오른쪽으로 내려 가면 최소값이 변해야 하므로, 현 node.val을 min param에 넣어줘 최소값을 부모노드 값으로 변화시킨다.
  if (node.right) {
    const isRightValidBST = dfsForValidBST(node.right, node.val, max);
    if (!isRightValidBST) {
      return false;
    }
  }

  return true;
}

console.log(isValidBST(root));