LeetCode 98(Validate Binary Search Tree, Python)

1. 문제 링크

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

Validate Binary Search Tree - LeetCode

2. 문제 설명

• 주어진 tree가 이진 탐색 트리(BST, Binary Search Tree)인지 확인하여 True, False 반환하는 문제
• 이진 탐색 트리란 아래 조건을 만족하는 Tree이다.
  • 왼쪽 서브트리의 모든 노드들은 현재 노드보다 작은 값
  • 오른쪽 서브트리의 모든 노드들은 현재 노드보다 큰 값
  • 왼쪽과 오른쪽 서브트리도 각각 이진 탐색 트리여야 함.
• True인 예시

 2

/ \

1 3

• False인 예시(3이 5보다 크지 않다.)

 5

/ \

1 4

   / \

  3   6

3. 처음 풀이

• 왼쪽 서브 트리의 값이 모두 현재 노드 보다 작아야하므로 왼쪽 서브 트리의 값 중 최댓값이 현재 값보다 작아야한다. 마찬가지로 오른쪽 서브 트리의 최솟값은 현재 노드 보다 커야한다.
• 따라서 주어진 노드를 루트로 하는 서브트리에서 최댓값, 최솟값을 찾는 함수를 만든 뒤, 재귀적으로 검사하는 방법을 생각하였다.

# 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:
        
				# 노드 없으면 유효
        if not root:
            return True

        # 하나 짜리도 유효
        if not root.left and not root.right:
            return True
        
				# 주어진 노드를 루트로 하는 서브트리에서 최대값을 찾는 함수        
        def findMax(root):
            if not root.left and not root.right:
                return root.val
            elif root.left and root.right:
                return max(root.val, findMax(root.left), findMax(root.right))
            elif root.right:
                return max(root.val, findMax(root.right))
            elif root.left:
                return max(root.val, findMax(root.left))
				
				# 주어진 노드를 루트로 하는 서브트리에서 최소값을 찾는 함수
        def findMin(root):
            if not root.left and not root.right:
                return root.val
            elif root.left and root.right:
                return min(root.val, findMin(root.left), findMin(root.right))
            elif root.left:
                return min(root.val, findMin(root.left))
            elif root.right:
                return min(root.val, findMin(root.right))

				# 왼쪽 서브트리의 최대값이 현재 노드보다 크면 False
        if root.left:
            if root.val <= findMax(root.left):
                return False

				# 오른쪽 서브트리의 최소값이 현재 노드보다 작으면 False
        if root.right:
            if root.val >= findMin(root.right):
                return False
        
				# 왼쪽 서브트리와 오른쪽 서브트리에 대해 재귀적으로 검사
        return self.isValidBST(root.left) and self.isValidBST(root.right)

4. 다른 풀이

• 중위순회시 오름차순으로 값이 나와야함.
• 중위순회하며 stack에 넣고 pop()하며 오름차순인지 확인하는 풀이.

# 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:
        # 중위 순회를 위한 스택
        stack = []
        # 이전에 방문한 노드의 값을 저장하는 변수
        prev = None
        
        # 중위 순회 시작
        while root or stack:
            # 현재 노드부터 가장 왼쪽 노드까지 스택에 추가
            while root:
                stack.append(root)
                root = root.left
            
            # 스택에서 노드를 꺼내어 현재 노드로 설정
            root = stack.pop()
            
            # 이전에 방문한 노드의 값과 비교하여 유효성 검사
            if prev is not None and root.val <= prev:
                return False
            
            # 현재 노드의 값을 이전에 방문한 노드로 설정
            prev = root.val
            
            # 오른쪽 서브트리로 이동
            root = root.right
        
        # 중위 순회 완료 후, 유효한 이진 탐색 트리임을 반환
        return True

 

---

• 재귀적으로 접근하되 최댓값, 최솟값을 변수로 넣어 좀 더 효율적인 코드

# 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 helper(node, lower=float('-inf'), upper=float('inf')):
            # 노드가 없으면 유효한 이진 탐색 트리임
            if not node:
                return True
            
            # 현재 노드의 값이 범위를 벗어나면 유효하지 않음
            if not lower < node.val < upper:
                return False
            
            # 왼쪽 서브트리와 오른쪽 서브트리에 대해 재귀적으로 검사
            return (helper(node.left, lower, node.val) and
                    helper(node.right, node.val, upper))

        # 최초에는 무한대 범위로 호출
        return helper(root)

5. 배운 점

• 중위 순회의 순서에 이런 의미가 있었다.
• 최댓값, 최솟값을 매번 새로 찾지 말고 한 단계 씩 내려갈 때 가질 수 있는 값의 범위의 양쪽 경계를 업데이트 해주면 된다.