LeetCode - 98. Validate Binary Search Tree - swift

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

Validate Binary Search Tree - LeetCode

 

 

주어진 노드를 이진 탐색 트리인지 판별하는 문제다.

이진 탐색 트리는 왼쪽 자식 노드는 부모 노드보다 작아야 하며,

오른쪽 자식 노드는 부모 노드보다 커야 한다.

뿐만 아니라, 자식의 자식들도 부모 노드보다 크거나 작아야 한다. 

 

즉 아래의 경우는 이진 탐색 트리가 아니다.  4는 6보다 작지만, 그 위의 root노드보다 커야 하기 때문이다. 

 

 

 

판별하는 방법은 많이 있겠지만, 나는 2개의 방법으로 풀어봤다. 

 

첫 번째는 lower, upper를 유지하면서 탐색하는 방법이다.

간단하게 [ 70, 50, 100, null, 60, null, null ] 이 있다고 가정하자.

처음 root노드는 -무한 ~ 무한 사이의 값 사이에서 비교하면 된다. 

즉 -무한  < 70 < 무한 이므로 root노드는 무조건 성립한다.

그다음 좌측 50 노드는 

upper가 무한에서 70으로 바뀌었다는 점에 주목하자.

즉, -무한 < 50 < 70 이 성립하므로 좌측 노드도 일치한다.

 

50 노드의 우측 자식 노드는 60인데, 

이제 lower 가 -무한에서 50으로 바뀌었다. 

 

마찬가지로 root노드의 우측 자식 노드 또한, lower가 70으로 바뀌었다. 

 

이렇게 좌측, 우측 탐색하면서 Lower, upper를 갱신하면서 값을 비교해나가면 된다.

 

class Solution {
    func isValidBST(_ root: TreeNode?) -> Bool {
        var isValid = true 
        func find(_ node: TreeNode?,_ lower: Int,_ upper: Int ) {
            if node == nil { return }
            if node!.val > lower, node!.val < upper {
                find(node?.left, lower, node!.val) 
                find(node?.right, node!.val, upper)
            } else {
                isValid = false 
                return 
            }
        }
        find(root, Int.min, Int.max)
        return isValid
    }
}

 

 

 

두 번째는 이진트리의 탐색방법 중 하나인 중위( inorder ) 탐색을 이용한다. 

이진 탐색 트리에서 중위 탐색을 하게 되면 탐색한 노드들의 값들이 오름차순이어야 한다는 특징을 갖고 있다. 

이진트리에서 중위 탐색을 한다고 해서 무조건 오름차순이 아니라, 이진 탐색 트리의 특성상, 오름차순일 수밖에 없다.

 

배열로 탐색한 숫자들을 저장하기보다는 가장 최근에 탐색한 값만 중요하므로, 

그러므로 중위 탐색을 하면서 저장한 값 보다 큰 경우에만 탐색하도록 한다. 

class Solution {
    func isValidBST(_ root: TreeNode?) -> Bool {
        var isValid = true
        var ans = Int.min
        
        func find(_ node: TreeNode?) {
            if node == nil { return }
            find(node?.left)
            if ans < node!.val {
                ans = node!.val
            } else {
                isValid = false
                return
            }
            find(node?.right)
        }
        find(root)
        return isValid
    }
}