(LeetCode) 98. Validate Binary Search Tree

Validate Binary Search Tree

• Explore : Interview > Top Interveiw Questions > Easy Collection
• 분류 : Trees
• 난이도 : Medium

Problem

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, 10^4].
• -2^31 <= Node.val <= 2^31 - 1

Solution

Exapnder

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun isValidBST(root: TreeNode?): Boolean {
        if (root == null) {
            return true
        }
        if (root.left == null && root.right == null) {
            return true
        }
        return recursive(root, null, null)
    }
    
    fun recursive(node: TreeNode?, min: Int?, max: Int?): Boolean {
        if (node == null) {
            return true
        }
        if (min != null && min <= node.`val`) {
            return false
            
        } 
        if (max != null && node.`val` <= max) {
            return false
        }
        return recursive(node.left, node.`val`, max) && recursive(node.right, min, node.`val`)
    }
}

Point of Thinking

• 이진트리의 조건을 검증하기 위해 min값과 max값을 들고다니면서 재귀로 처리한다.