Leetcode - Validate Binary Search Tree

Problem

Validate Binary Search Tree
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].
• -2³¹ <= Node.val <= 2³¹ - 1

Solution

JavaScript

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root) {
  //하위의 트리까지 모두 이진트리여야 하기 때문에 재귀로 접근
    return _isValidBST(root, -(2**31) - 1 , 2**31) // 제약조건에서 주어진 Node.val의 범위
  
    function _isValidBST(root, lower, higher) {
        if(!root) return true 
        
      // 위에 언급된 유효한 이진트리의 조건을 그대로 나열
        return root.val > lower && root.val < higher && _isValidBST(root.left, lower, root.val) && _isValidBST(root.right, root.val, higher)
    }
};

Feedback은 언제나 환영입니다🤗