[LeetCode]Validate Binary Search Tree

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

Validate Binary Search Tree - LeetCode

 

문제 분석

주어진 Tree가 유효한 Binary Search Tree인지 여부를 판단하는 문제입니다.

 

처음 시도한 답안 - 실패

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def traversal(root, direction, path, first_val):
            if not root:
                return True

            if root.left and root.val <= root.left.val:
                return False
            
            if root.right and root.val >= root.right.val:
                return False


            path.append((root.val, direction))
            print(path)
            if len(path) >= 2 and path[1][1] == 'left':
                if first_val < root.val:
                    print(")))")
                    return False

            if len(path) >= 2 and  path[1][1] == 'right':
                if first_val > root.val:
                    print("(((")
                    return False

            a = traversal(root.left, 'left', path, first_val)
            b = traversal(root.right, 'right', path, first_val)

            if a == False or b == False:
                return False

            path.pop()

            return True

        is_valid = traversal(root, '', [], root.val)

        return is_valid

접근 방법

1. 처음에 시도했던 방법입니다. 트리를 DFS 알고리즘으로 순회합니다.
2. 왼쪽인 경우에 부모 노드보다 왼쪽 자식의 값이 더 크다면 False 입니다.
3. 오른쪽인 경우에 부모 노드보다 오른쪽 자식의 값이 더 작다면 False 입니다.
4. 또한, 전달받은 direction에 따라서 루트노드와 비교하는 조건문도 추가합니다.

처음 접근한 방식은 현재 노드와 자식 노드의 값을 비교하고, 현재 노드와 루트 노드의 값을 비교해서 BST를 구하려고 했습니다. 하지만 이렇게 되는 경우 중간이 서브 트리들에서 조건을 만족하지 못하는 경우에는 판별할 수가 없어서 솔루션을 참고하게 되었습니다.

 

두번째로 시도한 답안

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def traversal(root, min_, max_):
            if not root:
                return True
            # 최솟값보다 적다면 BST 성립하지 않음
            if min_ is not None and root.val <= min_:
                return False
            # 최댓값보다 크다면 BST 성립하지 않음
            if max_ is not None and root.val >= max_:
                return False

            # 왼쪽으로 탐색할 때는 최댓값을 현재 노드의 값으로 설정. 왼쪽 자식 노드는 부모 노드보다 작아야 해서 최댓값이 부모노드가 되는 것임
            # 오른쪽으로 탐색할 때는 최솟값을 현재 노드의 값으로 설정. 오른쪽 자식 노드는 부모 노드보다 커야하므로 최솟값이 부모노드가 되는 것임
            return traversal(root.left, min_, root.val) and traversal(root.right, root.val, max_)

        return traversal(root, None, None)

접근 방법

1. 기본적으로 DFS 알고리즘을 이용합니다.
2. DFS 내부에서
   1. 최솟값이 존재할 때 현재 노드가 최솟값보다 적다면 False 입니다.
   2. 최댓값이 존재할 때 현재 노드가 최댓값보다 크다면 False 입니다.
   3. 왼쪽으로 재귀적으로 탐색하는 경우, 최솟값은 그대로 최댓값은 현재 노드의 값으로 설정합니다.
      (왼쪽 자식 노드는 부모 노드보다 작아야 해서 최댓값을 부모 노드의 값으로 설정함)
   4. 오른쪽으로 재귀적으로 탐색하는 경우, 최솟값은 현재 노드의 값으로 최댓값은 그대로 설정합니다.
      (오른쪽 자식 노드는 부모 노드보다 커야하므로 최솟값을 부노 노드의 값으로 설정함)
   5. 왼쪽, 오른쪽 모두 True를 리턴하는 경우에만 BST를 만족합니다.

우선, BST의 규칙을 생각해보면 다음과 같습니다.

1. 왼쪽 서브트리에 존재하는 모든 값들 < 현재 노드의 값이 되어야 합니다.
2. 오른쪽 서브트리에 존재하는 모든 값들 > 현재 노드의 값이 되어야 합니다.

따라서, 특정 노드의 값이 BST가 만족하는지 판단하려면 부모 및 조상노드들 중 최솟값과 최댓값 사이에 존재해야 합니다.

BST가 만족하는 조건 자체는 그림을 그려보면 쉽게 이해가 가지만 막상 구현하는 아이디어를 떠올리기엔 매우 어려웠던 것 같습니다.