[leetcode 98] Validate Binary Search Tree

98. Validate Binary Search Tree

https://leetcode.com/problems/binary-tree-inorder-traversal/

해결 과정

처음엔 예시만 보고, 왼쪽 노드 값 < 루트 노드 값 < 오른쪽 노드 값 이 맞는지 검사하는 문제로 이해하고 풀었는데

fail 이 난 케이스 [5,4,6,null,null,3,7]을 보니 오른쪽 서브 트리 노드 중 하나인 3이 루트 노드 5보다 작았을 때에도 false인 문제였다.

문제를 풀기 위해서는 해당 서브트리에서 가질 수 있는 최솟값 (오른쪽 서브트리를 위한) 과 최댓값 (왼쪽 서브트리를 위한) 을 파람으로 갖는 추가 메소드가 필요했다.

재귀로 풀었고, 탈출 조건은 1) 노드가 null 일 때 그리고 2) 노드 값 <= min, 3) 노드 값 >= max 일 때 이다.

코드

fun isValidBST(root: TreeNode?): Boolean {
    return checkValidBST(root, null, null)
}
    
private fun checkValidBST(root: TreeNode?, min: Int?, max: Int?) : Boolean {
    if(null == root) return true
    if(null != min && min >= root.`val`) return false
    if(null != max && max <= root.`val`) return false

    val leftResult = checkValidBST(root.left, min, root.`val`)
    val rightResult = checkValidBST(root.right, root.`val`, max)
    return leftResult && rightResult
}

배운 점

BST

왼쪽 서브트리(left subtree) 노드들 < 루트(root) 노드 < 오른쪽 서브트리(right subtree) 노드들