[LeetCode] 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.

예시

example1

Input: root = [2,1,3]
Output: true

example2

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.

---

풀기

왼쪽 노드의 값은 루트 노드보다 작아야 하고, 오른쪽 노드의 값은 루트 노드보다 커야한다는 내용이다.

여기에 틀린 값이 있는 경우 false를 리턴하고 조건을 모두 만족한다면 true를 리턴하는 내용.

 

나는 DFS로 재귀로 값을 체크해야 한다고 생각했다.

GPT는 좋은 친구라 더 좋은 방법이 있거나 내 코드에 최적화가 필요한게 있는지 확인해주므로 또 확인 요청을 했고

중위순회를 활용할 수도 있다는 내용을 받았다. (!! 빠밤)

 

참고로 나는 중위순회 까먹었다. (아~~ 자격증이나 전공 공부할 때 기억하고 끝나면 까먹는거 국룰 아님~~?~?~)

---

결과

1. DFS 사용

class Solution {
    fun isValidBST(root: TreeNode?): Boolean {
        return validate(root, Long.MIN_VALUE, Long.MAX_VALUE)
    }

    private fun validate(
        node: TreeNode?,
        min: Long,
        max: Long
    ): Boolean {
        if (node == null) {
            return true
        }

        if (node.`val` <= min || node.`val` >= max) {
            return false
        }

        return validate(node.left, min, node.`val`.toLong()) && validate(node.right, node.`val`.toLong(), max)
    }
}

GPT가 사실 코드 최적화를 도와주었다. (ㅎㅎ)

재귀를 통해 왼쪽의 경우 max에 루트 값을, 오른쪽의 경우 min에 루트 값을 넣어 비교하는 방식이다.

 

 

2. 중위순회(InOrder) 사용

기억이 안나서 인터넷에 검색해봤다.

• 전위순회(PreOrder) : root - left - right
• 중위순회(InOrder) : left - root - right
• 후위순회(PostOrder) : left - right - root

 위 순서대로 탐색한다.

    5
   / \
  3   7
 / \   \
2   4   8

 

GPT가 들어준 예제인데 위 트리를 중위순회 돌면 다음과 같다.

• 2 - 3 - 4 - 5 - 7 - 8

이게 오름차순이어야 한다는거다!

 

example2

LeetCode가 제시한 예제 2번을 가지고 중위순회를 돌아보면 다음과 같다.

• 1 - 5 - 3 - 4 - 6

오름차순이 아니다! 따라서 얘는 false가 return 되어야한다.

 

이제 이걸 코드로 구현해보자.

class Solution {
    private var prev = Long.MIN_VALUE

    fun isValidBST(root: TreeNode?): Boolean {
        return inorder(root)
    }

    private fun inorder(
        node: TreeNode?
    ): Boolean {

        if (node == null) {
            return true
        }

        // 왼쪽 서브트리 방문
        if (!inorder(node.left)) {
            return false
        }

        // 현재 노드가 이전 값보다 작거나 같으면 false
        if (node.`val` <= prev) {
            return false
        }
        prev = node.`val`.toLong()

        // 오른쪽 서브트리 방문
        return inorder(node.right)

    }
}