DaleStudy | Leetcode Study 2주차 - Validate Binary Search Tree

Leetcode Study

문제

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 strictly less than the node's key.
The right subtree of a node contains only nodes with keys strictly 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인지 확인하는 것이다. 즉, 현재 원소의 왼쪽에는 더 작은 수가 들어가고 현재 원소의 오른쪽에는 더 큰 수가 들어가면 true이고, 그게 아니라면 false를 리턴하면된다. 

보통 BST를 풀 땐 함수를 하나 더 만들어서 그 함수를 재귀시켜주면 되는데, 재귀의 조건을 잘 설정해야한다. 

 

function isValidBST(root: TreeNode | null): boolean {
    return validateBSTHelper(root, -Infinity, Infinity);
};

const validateBSTHelper = (root: TreeNode | null, minValue: number, maxValue: number): boolean => {
    if (root === null) { return true; }
    if (root.val <= minValue || root.val >= maxValue) { return false; }
    const leftIsValid = validateBSTHelper(root.left, minValue, root.val);
    return leftIsValid && validateBSTHelper(root.right, root.val, maxValue);
}

 

 

Link: https://leetcode.com/problems/validate-binary-search-tree/description/