[Leetcode 아주 상세한 문제풀이] 98. Validate Binary Search Tree – 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 98번 문제 Validate binary search tree 다.

우선 문제를 살펴보자.

 

리트코드 98번 문제 Validate binary search tree 링크

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

Validate Binary Search Tree - LeetCode

 

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, 104].
-231 <= Node.val <= 231 - 1

 

 

문제 설명

문제를 간략히 살펴보자. Binary tree를 이루는 root가 인풋으로 주어진다. 이때 이것이 valid binary search tree (BST) 인지 판단하라는 문제다. 여기서 BST에 대한 조건이 다음과 같이 주어져있다.

1) 해당 노드의 왼쪽 subtree 노드들은 해당 노드 값보다 작은 값들을 가져야 한다.

2) 해당 노드의 오른쪽 subtree 노드들은 해당 노드 값보다 큰 값들을 가져야 한다.

3) 왼쪽과 오른쪽 subtree 역시 binary search trees 여야 한다.

이해를 돕기 위해 문제 예시 1번을 살펴보자. Binary tree의 root는 2이고 왼쪽 노드는 1 그리고 오른쪽 노드는 3으로 주어졌다. BST의 조건을 따져보면 우선 왼쪽 subtree의 노드 1은 2보다 작고 오른쪽 subtree의 노드 3을 2보다 크다. 더불어 왼쪽과 오른쪽 subtree는 child node가 없어 binary search tree다. 따라서 인풋으로 주어진 [2, 1, 3] binary tree는 BST 조건에 부합함을 알 수 있다. 문제를 이해하기 어렵지 않으니 곧바로 문제를 풀어보도록 하자.

 

 

문제 접근법

이 문제를 해결하기 위하여 우리는 재귀 함수를 이용할 것이다.

문제에서 요구하는 바는 주어진 binary tree가 BST 임을 판단해야 한다.

이때 BST 조건을 만족하기 위해서는 root 노드 뿐만 아니라 subtree의 노드들도 확인해야 한다.

따라서 이 문제를 해결하는 아이디어는 주어진 binary tree를 탐색할 때 왼쪽 subtree의 노드들이 root 값 보다 작은지, 그리고 오른쪽 subtree의 노드들이 root 값 보다 큰지 확인하는 것이다.

한 가지 유의할 점은 tree 아래쪽으로 탐색을 할 때 노드 값들이 원하는 범위 (range)에 있는지를 확인해야 한다는 것이다.

예를 들어 다음과 같은 binary tree가 주어졌다고 생각해보자.

 

 

 

 

 

우선 우리는 가장 상단에 위치한 노드 5부터 시작을 한다.

이때 범위는 -inf (마이너스 무한대) 부터 +inf (플러스 무한대)로 설정한다.

노드 5는 이 범위 안에 들기 때문에 다음 탐색을 진행한다.

다음 탐색에서 왼쪽 subtree에서 노드 1을 만나게 된다.

이때 우리는 왼쪽 subtree가 BST에 부합되는지 판단할 때 그 범위를 마이너스 무한대 부터 5 사이로 좁혀 판단할 수 있다. 그 이유는 BST의 조건에 따라 왼쪽 subtree의 노드들은 그 root 값 (=5) 보다 작아야 하기 때문이다.

따라서 노드 1의 경우 이 범위 안에 들기 때문에 BST 조건에 부합된다고 할 수 있다.

마찬가지로 오른쪽 subtree가 BST에 부합되는지 판단할 때 그 범위를 5 부터 플러스 무한대 사이로 좁혀 판단할 수 있다.

따라서 노드 4의 경우 이 범위안에 들지 않으므로 BST 조건에 부합하지 않음을 알 수 있다.

다른 subtree를 탐색할 필요 없이 BST 조건에 부합하지 않는 노드를 발견했으므로 탐색을 멈추고 BST가 아님을 리턴하면 된다.

이제 코드로 한 번 살펴보자.

 

 

문제 풀이

Binary tree를 표현하기 위한 class를 선언해준다. (line 1-5)

이는 파이썬에서 일반적으로 사용되는 표현식이니 익숙해 지도록 하자.

인풋값을 입력받을 함수를 정의해 준다. (line 7)

이제 재귀함수를 만들어줄 것인데 탐색하는 노드값과 최대/최소값을 인풋으로 입력받는다. (line 8)

만약 해당 노드가 존재하지 않는다면 true를 리턴하고 종료한다. (line 10-11)

위에서 설명했듯이 탐색하고 있는 노드 값은 BST 조건에 부합하는 범위 안에 존재해야 한다.

따라서 그 값이 최소값보다 작거나 혹은 최대값보다 크다면 그 범위를 벗어나는 것이기 때문에 이 경우 false를 리턴하고 종료한다. (line 14-15)

이제 이 과정을 재귀적으로 실행할 것이다.

즉 왼쪽과 오른쪽 subtree에 대해서 BST 조건에 부합하는지 탐색을 한다.

이때 중요한 것은 왼쪽 subtree의 경우 최대 값을 지금 막 탐색한 노드 값으로 업데이트 해주고,

오른쪽 subtree의 경우 최소 값을 지금 막 탐색한 노드 값으로 업데이트 해줘야 한다는 점이다. (line 18-19)

이 재귀적 탐색과정을 진행하는 와중에 탐색 노드 값이 해당 범위를 넘어간다면 false가 리턴되고 종료한다.

반대로 모든 노드 값이 해당 범위에 존재해 BST 조건을 만족한다면 중간에 false가 리턴되지 않고 최종적으로 true가 리턴되고 종료된다. (line 21)

 

 

문제 풀이 코드

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
def isValidBST(root):
    def validate(node, low=-float('inf'), high=float('inf')):
        # An empty tree is a valid BST
        if not node:
            return True
 
        # The current node's value must be between low and high
        if node.val <= low or node.val >= high:
            return False
 
        # Recursively validate the left and right subtree
        return (validate(node.left, low, node.val) and
                validate(node.right, node.val, high))
 
    return validate(root)
 
# Example usage
root1 = TreeNode(2)
root1.left = TreeNode(1)
root1.right = TreeNode(3)
 
root2 = TreeNode(5)
root2.left = TreeNode(1)
root2.right = TreeNode(4)
root2.right.left = TreeNode(3)
root2.right.right = TreeNode(6)
 
print(isValidBST(root1))  # Output: True
print(isValidBST(root2))  # Output: False
 

 

 

관련 문제

리트코드 102번 Binary tree level order traversal 문제 풀이 (링크)

리트코드 104번 Maximum depth of binary tree 문제 풀이 (링크)

리트코드 105번 Construct binary tree from preoder and inorder traversal 문제 풀이 (링크)

리트코드 124번 Binary tree maximum path sum 문제 풀이 (링크)

리트코드 208번 Implement tree (Prefix tree) 문제 풀이 (링크)

리트코드 212번 Word search 2 문제 풀이 (링크)

리트코드 226번 Invert/flip binary tree 문제 풀이 (링크)

리트코드 235번 Lowest common ancestor of BST 문제 풀이 (링크)

리트코드 572번 Subtree of another tree 문제 풀이 (링크)

 

98. Validate Binary Search Tree