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

問題の説明

バイナリ検索ツリーノードをあげます.問題は、バイナリ検索ツリーが正しいかどうかを検証することです.
BSTツリーの親ノード標準の左側の子ノードは小さく、右側の子ノードは大きくなければなりません.この法則は木が下に下がるほど適用される.
1番目のツリー2,1,3はtrue、2番目のツリーはleaf Nodeです.3はfalseです.3 rootNode、すなわち5より大きい必要があります.(右側にあるので)
このようなツリーの特性に対して、最小値、最大値を他の値に割り当て続け、問題を解決する必要があります.
私がこの問題をできなかった理由は1です.ルートツリーを基準に左右の2つの領域を分割し、左側の領域はmaxがrootNodeより小さく固定され、右側の領域はmin=rootNodeと指定されると、ツリー全体が適用されると誤って判断されます->ノードごとにminor max値が変更されます.左側のサブノードの場合はmax値を親ノード値として指定し、右側のサブノードの場合はmin値を親ノード値として指定します.

min、最大変数をグローバル変数に設定します.

上述したように、このような問題ではmax、minをグローバルとして定義することはできず、関数パラメータとして使用すべきである.ツリーからツリーへの1回の操作で、動作で使用される最大値と最小値がグローバル変数として共有されている場合、ツリーが1つのreftノードから親ノードにアップロードされ、次のlightノードでは最小値が左の値として共有され、パラメータに入れると右のときに左のサブノードのdsf関数が呼び出されるときに最小になるからです.max値ではなく、ルートノードの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));